## 2 questions

Expand Messages
• Hi All, 1) I know this is a moving target, but as people continue to calculate pi (3.14...) to ever increasing number of decimal places surely someone out
Message 1 of 27 , Sep 24, 2002
Hi All,
1) I know this is a moving target, but as people continue to
calculate pi (3.14...) to ever increasing number of decimal places
surely someone out there must be enumerating the function pi (The
number of primes less than n)
So my first question is

What is the largest number n such that pi(n) is known?

I don't mind that the answer will have changed by the time I read the
If no one is willing to be specific an order of magnitude will do
(e.g 10^16)

2) The prime community concentrates on finding larger and larger
primes. I have a question dealing with smallest.

What is the smallest prp?

(By which I mean number known to be prp but beyond our current
skills/effort to prove prime (or composite)).
For Jon Perry's benefit (if practical) we could treat this as a game.
Someone supply a prp (whose primality is non-trivial to determine
(say a week of pII cpu time)) to which someone can answer with either
a smaller example or with proof of the numbers
primeness/compositeness thus eliminating it from contention.

Cheers
Ken
• ... I think 10^22 is the current published record. +---------------------------------------------------------+ ...
Message 2 of 27 , Sep 24, 2002
At 03:02 AM 9/25/2002 +0000, Ken Davis wrote:

>What is the largest number n such that pi(n) is known?

I think 10^22 is the current published record.

+---------------------------------------------------------+
| Jud McCranie |
| |
| Programming Achieved with Structure, Clarity, And Logic |
+---------------------------------------------------------+

[Non-text portions of this message have been removed]
• ... The problem with any such contest is that it can take 20 minutes to find a number, and 15 seconds to prove it PRP, that is basically impossible to prove
Message 3 of 27 , Sep 24, 2002
On Wed, 25 Sep 2002 03:02:37 -0000, Ken Davis wrote:

>(By which I mean number known to be prp but beyond our current
>skills/effort to prove prime (or composite)).
>For Jon Perry's benefit (if practical) we could treat this as a game.
>Someone supply a prp (whose primality is non-trivial to determine
>(say a week of pII cpu time)) to which someone can answer with either
>a smaller example or with proof of the numbers
>primeness/compositeness thus eliminating it from contention.

The problem with any such "contest" is that it can take 20 minutes to
find a number, and 15 seconds to prove it PRP, that is basically
impossible to prove prime in any reasonable length of time. However,
the vast majority of such numbers *are* prime, and thus cannot be
proven composite.

Nathan
• HI Nathan, I realised the vast majority of prp s are prime but proving them prime would also eliminate them as the smallest prp. I would think the conditions
Message 4 of 27 , Sep 24, 2002
HI Nathan,
I realised the vast majority of prp's are prime but proving them
prime would also eliminate them as the smallest prp.
I would think the conditions you state would make the question ripe
for a contest.
If prps can be found easily but their proof of primality is beyond
our current technical ability then stating a given prp to be the
smallest should be fine. Eventually we should zero in to a number
where it becomes practical to prove and then the current smallest prp
could move both ways.
Perhaps we can keep track of the 10 (100) smallest in the same way we
keep track of the largest.
Ken

--- In primenumbers@y..., Nathan Russell <nrussell@a...> wrote:
> On Wed, 25 Sep 2002 03:02:37 -0000, Ken Davis wrote:
>
> >(By which I mean number known to be prp but beyond our current
> >skills/effort to prove prime (or composite)).
> >For Jon Perry's benefit (if practical) we could treat this as a
game.
> >Someone supply a prp (whose primality is non-trivial to determine
> >(say a week of pII cpu time)) to which someone can answer with
either
> >a smaller example or with proof of the numbers
> >primeness/compositeness thus eliminating it from contention.
>
> The problem with any such "contest" is that it can take 20 minutes
to
> find a number, and 15 seconds to prove it PRP, that is basically
> impossible to prove prime in any reasonable length of time.
However,
> the vast majority of such numbers *are* prime, and thus cannot be
> proven composite.
>
> Nathan
• ... The problem here is this: you give me a PRP which is not provable within the next year. As has been pointed out, this is possible in under an hour. I
Message 5 of 27 , Sep 24, 2002
Ken Davis wrote:
> I realised the vast majority of prp's are prime but proving them
> prime would also eliminate them as the smallest prp.
> I would think the conditions you state would make the question ripe
> for a contest.
> If prps can be found easily but their proof of primality is beyond
> our current technical ability then stating a given prp to be the
> smallest should be fine. Eventually we should zero in to a number
> where it becomes practical to prove and then the current smallest prp
> could move both ways.

The problem here is this: you give me a PRP which is not provable
within the next year. As has been pointed out, this is possible
in under an hour.

I notice your "record" (call it N). I search for the first PRP in
the sequence N-2, N-4, N-6, ... I submit my finding as the new
"record". This took me under an hour as well.

And then you better my "record" and find the next smallest PRP.

Do you see where this is going?

Any "record smallest PRP" takes days, weeks, or years to prove
prime, but the same "record smallest PRP" can be bettered in
minutes.
• ... http://numbers.computation.free.fr/Constants/Primes/countingPrimes.html ... Well, we have a lot of interesting small PRP s which are hard to be proven
Message 6 of 27 , Sep 25, 2002
> So my first question is
>
> What is the largest number n such that pi(n) is known?

http://numbers.computation.free.fr/Constants/Primes/countingPrimes.html

> What is the smallest prp?
>
> (By which I mean number known to be prp but beyond our current
> skills/effort to prove prime (or composite)).

Well, we have a lot of interesting small PRP's which are hard to be proven prime.

floor((pi-3)*10^6205) - would take a year to prove
http://research.microsoft.com/~pleyland/primes/xyyx.htm - there are some week-provable, but still not proven

and many others...

Best,

Andrey

[Non-text portions of this message have been removed]
• ... What makes this more interesting than some random 6000 digit number? Is there something especially difficult about it?
Message 7 of 27 , Sep 25, 2002
On Wed, 25 Sep 2002, Andrey Kulsha wrote:
> Well, we have a lot of interesting small PRP's which are hard to be
> proven prime.
> floor((pi-3)*10^6205) - would take a year to prove

What makes this more interesting than some random 6000 digit number? Is
there something especially difficult about it?
• ... pi(4*10^22) = 783,964,159,847,056,303,858 according to: http://numbers.computation.free.fr/Constants/Primes/Pix/results.html They tried to compute
Message 8 of 27 , Sep 25, 2002
> What is the largest number n such that pi(n) is known?

pi(4*10^22) = 783,964,159,847,056,303,858 according to:
http://numbers.computation.free.fr/Constants/Primes/Pix/results.html
They tried to compute pi(10^23) and got around
1,925,320,391,606,818,006,727 but the computation failed.
Note pi(n) can be computed directly without computing all primes
below n.

> What is the smallest prp?
>
> (By which I mean number known to be prp but beyond our current
> skills/effort to prove prime (or composite)).

The biggest "general" prime is 10^5019+43157099231631693 proved by
Giovanni and Marco La Barbera with Primo by Marcel Martin.
Here "general" roughly means the prime does not have an easily
provable form and a general method is used. It took 13 weeks to
prove with ECPP as implemented by Primo.

I now claim the "record" for the "smallest prp":
10^5019+43157099231631693+1746
This is the smallest prp bigger than any prime proved with a general
method like ECPP.
The search took less than 2 minutes to set up and 5 minutes to run
(I got lucky, the expectation was around 33 minutes). The prp-test
of the "record" took 5 seconds.
With current programs my "record" can apparently only be beaten by
running Primo for around 13 weeks to prove a bigger prime and then
use an extra 33 minutes or so to find the next prp.
Congratulations are in order :-)

I agree with other responders: This record is meaningless.
I have attempted to put a shread of meaning into it and I think I
failed.

Would I get the pi(n)-record by finding the next prime after the
existing record?
Or even by just proving n+1 is composite?
This also appears meaningless, the next 1000 primes can probably be
found in seconds. A recognized record should be a big improvement
over the old, e.g. 10% higher. This should be plenty to ensure that
it is not worth-while to build on the old record since a faster
method exists to compute pi(n) directly. Actually I think 0.001%
improvement is enough to ensure this but I guess nobody would spend
a lot of time on such an improvement.
--
Jens Kruse Andersen
• This brings up the crux of why I asked the question in the first place. I wanted to see what size random numbers could be practically proven to be prime.
Message 9 of 27 , Sep 25, 2002
This brings up the crux of why I asked the question in the first
place.
I wanted to see what size "random" numbers could be "practically"
proven to be prime.

Nearly all the prime records are N+/-1 because theorems exist that
allow primality proofs if you can factorise (to a third of its digits
(i think)) the previous or next number.

Now you say floor((pi-3)*10^6205) could be proven prime within a year
How?

4361!11-5581 is is Fermat and Lucas PRP and only has 1273 digits but
I wouldn't have a clue how to prove it prime within a year. Can it be
done?

Plus (and I know the encryption is based on the difficulty of
factoring not proving primality) but I read somewhere that primality
wasn't actually necessary and that some of the large primes used may
in fact only be prps.)

So if I was to find a "random" prp (just a string of digits not
generated by any formula) up to what size would it be practical to
prove it prime?

--- In primenumbers@y..., Carl Devore <devore@m...> wrote:
>
>
> On Wed, 25 Sep 2002, Andrey Kulsha wrote:
> > Well, we have a lot of interesting small PRP's which are hard to
be
> > proven prime.
> > floor((pi-3)*10^6205) - would take a year to prove
>
> What makes this more interesting than some random 6000 digit
number? Is
> there something especially difficult about it?
• ... You should have just asked that then. :-) About 5000 - 6000 digits, very roughly speaking, using Marcel Martin s program Primo. As previous responses in
Message 10 of 27 , Sep 25, 2002
Ken Davis wrote:
>
> This brings up the crux of why I asked the question in the first
> place.
> I wanted to see what size "random" numbers could be "practically"
> proven to be prime.
>

You should have just asked that then. :-)

About 5000 - 6000 digits, very roughly speaking, using Marcel Martin's
program Primo. As previous responses in this thread indicated,
Primo has been used to prove the primality of a "random"
(non-special-form) number with 5020 digits.

See:

http://www.znz.freesurf.fr/pages/primo.html

Be prepared to spend weeks or months to prove the primality of
such a large number...

Primo can easily do 1273 digits. Someone who uses Primo on a
regular basis can probably tell you how long it would take,
certainly it will be far far less than a year.
• ... A number of the form a^k+b *IS* more interesting, with interest level increasing with decreasing a and b and increasing with k. So why do you choose Pi-3
Message 11 of 27 , Sep 25, 2002
On Thu, 26 Sep 2002, Marcel Martin wrote:
> >What makes this more interesting than some random 6000 digit number? Is
> >there something especially difficult about it?
>
> They are not more interesting but there are at least two reasons to
> choose numbers like N = a^k + b or N = some decimals of pi or of e
> instead of a true random number.

A number of the form a^k+b *IS* more interesting, with interest level
increasing with decreasing a and b and increasing with k.

So why do you choose Pi-3 rather than just Pi?

> 1) A true random number will always look suspicious. I agree, this
> is not rational.

Seems rational to me. Considering the glory associated with large primes,
it is very rational to suspect that the numbers have been cooked up. It
is like any other sporting event.
• ... Because I did not guess your answer. But now that you mentioned it, it seems like a very rational explanantion. Why does it seem *not* rational to you
Message 12 of 27 , Sep 25, 2002
On Thu, 26 Sep 2002, Marcel Martin wrote:
> >> 1) A true random number will always look suspicious. I agree, this
> >> is not rational.
>
> >Seems rational to me. Considering the glory associated with large primes,
> >it is very rational to suspect that the numbers have been cooked up.
>
> Why did you ask this question then?
> >What makes this more interesting than some random 6000 digit number?

mentioned it, it seems like a very rational explanantion. Why does it
seem *not* rational to you that people would cheat?

> A 'cooked' number would immediately be detected just by looking at the
> certificate.

Please explain. By "cooked", I mean cheating by using a number that
appears random but actually has some form that makes its primality easier
to prove than other random primes of the same length.
• ... Isn t that extremely short time a sign that the number has some special structure such that its primality is especially easy to prove? Perhaps that
Message 13 of 27 , Sep 25, 2002
On Wed, 25 Sep 2002, jkand71 wrote:
> The biggest "general" prime is 10^5019+43157099231631693 proved by
> Giovanni and Marco La Barbera with Primo by Marcel Martin.
> Here "general" roughly means the prime does not have an easily
> provable form and a general method is used. It took 13 weeks to
> prove with ECPP as implemented by Primo.
>
> I now claim the "record" for the "smallest prp":
> 10^5019+43157099231631693+1746
> This is the smallest prp bigger than any prime proved with a general
> method like ECPP.
> The search took less than 2 minutes to set up and 5 minutes to run
> (I got lucky, the expectation was around 33 minutes). The prp-test
> of the "record" took 5 seconds.

Isn't that extremely short time a sign that the number has some special
structure such that its primality is especially easy to prove? Perhaps
that special structure is not known.

> With current programs my "record" can apparently only be beaten by
> running Primo for around 13 weeks to prove a bigger prime and then
> use an extra 33 minutes or so to find the next prp.
> Congratulations are in order :-)
>
> I agree with other responders: This record is meaningless.
> I have attempted to put a shread of meaning into it and I think I
> failed.
>
> Would I get the pi(n)-record by finding the next prime after the
> existing record?
> Or even by just proving n+1 is composite?
> This also appears meaningless, the next 1000 primes can probably be
> found in seconds. A recognized record should be a big improvement
> over the old, e.g. 10% higher. This should be plenty to ensure that
> it is not worth-while to build on the old record since a faster
> method exists to compute pi(n) directly. Actually I think 0.001%
> improvement is enough to ensure this but I guess nobody would spend
> a lot of time on such an improvement.
>
• ... I think on any computer you can buy new today, it would be done fairly easily in an overnight run. On my P3-600, 1000 digits takes a few hours. Nathan
Message 14 of 27 , Sep 25, 2002
On Wed, 25 Sep 2002 20:09:26 -0400, Jack Brennen wrote:

>Primo can easily do 1273 digits. Someone who uses Primo on a
>regular basis can probably tell you how long it would take,
>certainly it will be far far less than a year.

I think on any computer you can buy new today, it would be done fairly
easily in an overnight run.

On my P3-600, 1000 digits takes a few hours.

Nathan
• On Wed, 25 Sep 2002 22:14:20 -0400 (EDT), Carl Devore ... ECPP takes roughly the same time for all primes of a given length, to the best of my knowledge. The
Message 15 of 27 , Sep 25, 2002
On Wed, 25 Sep 2002 22:14:20 -0400 (EDT), Carl Devore
<devore@...> wrote:

>Please explain. By "cooked", I mean cheating by using a number that
>appears random but actually has some form that makes its primality easier
>to prove than other random primes of the same length.

ECPP takes roughly the same time for all primes of a given length, to
the best of my knowledge. The numbers that take less time to prove
usually do so because a whole different algorithm can be used, e.g.
the N-1, N+1, or LL tests.

Nathan
• ... Running a prp-test on any 5020 digit prime will take approximately the same amount of time (5 seconds in this case), regardless of its structure or form.
Message 16 of 27 , Sep 25, 2002
Carl Devore wrote:
> On Wed, 25 Sep 2002, jkand71 wrote:
> > I now claim the "record" for the "smallest prp":
> > 10^5019+43157099231631693+1746
> > This is the smallest prp bigger than any prime proved with a general
> > method like ECPP.
> > The search took less than 2 minutes to set up and 5 minutes to run
> > (I got lucky, the expectation was around 33 minutes). The prp-test
> > of the "record" took 5 seconds.
>
> Isn't that extremely short time a sign that the number has some special
> structure such that its primality is especially easy to prove? Perhaps
> that special structure is not known.
>

Running a prp-test on any 5020 digit prime will take approximately
the same amount of time (5 seconds in this case), regardless of its
structure or form.

The fact that 5 minutes was required rather than 33 minutes simply
indicates that the prime gap of 1746 was short compared to the
average gap near 10^5019, which is about 11557.
• ... general ... run ... test ... special ... Perhaps ... I used Primeform/GW for the prp-testing. Any 5020-digit number, prime or composite, will take
Message 17 of 27 , Sep 25, 2002
--- In primenumbers@y..., Carl Devore <devore@m...> wrote:
>
> On Wed, 25 Sep 2002, jkand71 wrote:
> > I now claim the "record" for the "smallest prp":
> > 10^5019+43157099231631693+1746
> > This is the smallest prp bigger than any prime proved with a
general
> > method like ECPP.
> > The search took less than 2 minutes to set up and 5 minutes to
run
> > (I got lucky, the expectation was around 33 minutes). The prp-
test
> > of the "record" took 5 seconds.
>
> Isn't that extremely short time a sign that the number has some
special
> structure such that its primality is especially easy to prove?
Perhaps
> that special structure is not known.

I used Primeform/GW for the prp-testing. Any 5020-digit number,
prime or composite, will take practically the same time to prp-test
(without trial factoring): Around 5 seconds on my PC. The time for
the algorithm is simply a function of the size and independent of
the specific number unlike some primality proving algorithms.
I specifically mentioned the timings to show how meaningless
a "record" for the smallest prp would be.
If some necessarily unfair rule for a record is chosen then my idea
I doubt I could convince anyone to recognize me as a record-holder.
I don't even recognize myself.

Ken Davis wrote:
> 4361!11-5581 is is Fermat and Lucas PRP and only has 1273 digits
but
> I wouldn't have a clue how to prove it prime within a year. Can it
be
> done?

Primo should typically take a few hours on 1273 digits with a new
PC. Someone will probably do it once it has been posted here.
The biggest prime I have proven with Primo is actually 3057 pi
decimals, part of pi as a concatenation of the smallest contiguous
different primes:
http://www.primepuzzles.net/problems/prob_018.htm
I then found a 14650-digit prp which would take decades or centuries
to prove with Primo if it even works on this size.
With all due respect to Marcel Martin, something better has probably
been developed before that. Maybe someone has even made a practical
use of AKS - naah, that should have a smiley :-)
--
Jens Kruse Andersen
• ... Which is why I commend x^y+y^x as ideal test cases for primality provers. they have very short formulae, are self-evidently not cooked (raw?) and have
Message 18 of 27 , Sep 26, 2002
> 1) A true random number will always look suspicious. I agree, this
> is not rational.
>
> 2) So that a record is known, it must be published. And the fact
> we can compress a number as a small formula makes its publication
> easier, i.e., it gives less work to prime database managers :-)

Which is why I commend x^y+y^x as ideal test cases for primality provers. they have very short formulae, are self-evidently not "cooked" (raw?) and have no useful divisibility properties (known to me anyway) which makes proving them prime any easier than random numbers.

Francois Morain seems to agree with me. He's using them as test cases for his ECPP program.

See http://research.microsoft.com/~pleyland/primes/xyyx.htm for details.

Paul
• ... This number would be on of the best of Prime Curios: http://primes.utm.edu/curios/page.php?short=14159...07021%20(547-digits) Best, Andrey [Non-text
Message 19 of 27 , Sep 26, 2002
> > Well, we have a lot of interesting small PRP's which are hard to be
> > proven prime.
> > floor((pi-3)*10^6205) - would take a year to prove
>
> What makes this more interesting than some random 6000 digit number? Is
> there something especially difficult about it?

This number would be on of the best of Prime Curios:

http://primes.utm.edu/curios/page.php?short=14159...07021%20(547-digits)

Best,

Andrey

[Non-text portions of this message have been removed]
• 1) Which number do the most primes end in {1, 3, 7, or 9}? I m guessing 7 but does someone know? and a similar one 2) If you input a really long stream of
Message 20 of 27 , Sep 25, 2004
1) Which number do the most primes end in {1, 3, 7, or 9}?
I'm guessing 7 but does someone know?
and a similar one
2) If you input a really long stream of numbers into 6n+1 and 6n-1,
which would yield more prime numbers?

than a normal one...

Plano9
• ... As the numbers go to infinity, they approach the same ratio. ... As n goes to infinity, their ratio goes to 1.
Message 21 of 27 , Sep 25, 2004
At 06:30 PM 9/25/2004, plano9 wrote:
>1) Which number do the most primes end in {1, 3, 7, or 9}?

As the numbers go to infinity, they approach the same ratio.

>2) If you input a really long stream of numbers into 6n+1 and 6n-1,
>which would yield more prime numbers?

As n goes to infinity, their ratio goes to 1.
• In a message dated 25/09/2004 23:33:36 GMT Daylight Time, plano9@yahoo.com ... Counts of the number of primes
Message 22 of 27 , Sep 26, 2004
In a message dated 25/09/2004 23:33:36 GMT Daylight Time, plano9@...
writes:

> 1) Which number do the most primes end in {1, 3, 7, or 9}?
> I'm guessing 7 but does someone know?
> and a similar one
> 2) If you input a really long stream of numbers into 6n+1 and 6n-1,
> which would yield more prime numbers?
>

Counts of the number of primes < 10^13 of your 2 forms can be found in my
NMBRTHRY post:
http://listserv.nodak.edu/scripts/wa.exe?A2=ind0403&L=nmbrthry&P=2486

1)
[10,1]=86516370000
[10,3]=86516427946
[10,5]=1
[10,7]=86516367790
[10,9]=86516371101

2)
[6,1]=173032692013
[6,3]=1
[6,5]=173032844824

-Mike Oakes

[Non-text portions of this message have been removed]
• Hello, fellow primenumbers group members.  I have a couple of questions, one specific one on a certain class of numbers and one on software.    The first
Message 23 of 27 , Apr 6, 2011
Hello, fellow primenumbers group members.  I have a couple of questions, one specific one on a certain class of numbers and one on software.

The first question I have is connected with an observation.  It appears that to the level of complete evaluation the numbers for any n that are sums of two disjoint products of the first n primes (such as 2*3*11+5*7 for n=5) are such that if one is randomly selected the probability of primality is consistently about 0.93^n.  I'm wondering if there is such a limiting value close to 0.93, if anyone knows, for reasonably simple heuristic reasons.

The second question concerns PARI/GP's ispseudoprime( ) function.  As far as all I have done experimentally shows, it seems I could possibly run tests using this until 'the cows come home' without getting a false positive. Does anybody have info on the heuristic probability by size of such and know if one has ever been found?  Does anyone know exactly which pseudoprime tests exactly go into the function?  Does it seem reasonable to submit the counts by n for the first question to OEIS with a caveat this function was employed, or should it be considered overly optimistic on the function and simply withheld aside from values that have sustained stronger attack?

James G. Merickel

[Non-text portions of this message have been removed]
• ad Q2: Did you try ... You should get something equivalent to http://pari.math.u-bordeaux.fr/dochtml/html/Arithmetic_functions.html#ispseudoprime Maximilian
Message 24 of 27 , Apr 7, 2011
Did you try

> ?? ispseudoprime

You should get something equivalent to
http://pari.math.u-bordeaux.fr/dochtml/html/Arithmetic_functions.html#ispseudoprime

Maximilian

On Wed, Apr 6, 2011 at 10:42 PM, James Merickel <merk7777777@...> wrote:
> Hello, fellow primenumbers group members.  I have a couple of questions, one specific one on a certain class of numbers and one on software.
>  (...)
> The second question concerns PARI/GP's ispseudoprime( ) function.  As far as all I have done experimentally shows, it seems I could possibly run tests using this until 'the cows come home' without getting a false positive. Does anybody have info on the heuristic probability by size of such and know if one has ever been found?  Does anyone know exactly which pseudoprime tests exactly go into the function?  Does it seem reasonable to submit the counts by n for the first question to OEIS with a caveat this function was employed, or should it be considered overly optimistic on the function and simply withheld aside from values that have sustained stronger attack?
>
> James G. Merickel
>
• ... This is part of the information contained in the above reference: If flag = 0, checks whether x is a Baillie-Pomerance-Selfridge-Wagstaff pseudo prime
Message 25 of 27 , Apr 9, 2011
--- In primenumbers@yahoogroups.com, Maximilian Hasler <maximilian.hasler@...> wrote:
>
> Did you try
>
> > ?? ispseudoprime
>
> You should get something equivalent to
> http://pari.math.u-bordeaux.fr/dochtml/html/Arithmetic_functions.html#ispseudoprime
>

This is part of the information contained in the above reference:

"If flag = 0, checks whether x is a Baillie-Pomerance-Selfridge-Wagstaff pseudo prime (strong Rabin-Miller pseudo prime for base 2, followed by strong Lucas test for the sequence (P,-1), P smallest positive integer such that P^2 - 4 is not a square mod x)".

I am curious as to the nuts and bolts of applying these techniques.
Are there pages of abstract complexities that need to be computed
to get a result, or does the whole thing boil down to a few lines
of code?

Thanks a million, Max.

Aldrich
• I discussed the Baillie-Wagstaff primality checker at my blog . Here s the latest
Message 26 of 27 , Apr 12, 2011
I discussed the Baillie-Wagstaff primality checker at my blog
<http://programmingpraxis.com/2010/01/26/primality-checking-revisited/>
. Here's the latest version of source code, in Scheme, which differs
slightly from the original entry; it's more than "a few lines" of code,
but not too long:
(define (prime? n) (letrec ( (expm (lambda (b e m) (let ((times
(lambda (x y) (modulo (* x y) m)))) (cond ((zero? e) 1) ((even?
e) (expm (times b b) (/ e 2) m)) (else (times b (expm (times b b)
(/ (- e 1) 2) m))))))) (digits (lambda (n) (let loop ((n n) (ds
'())) (if (zero? n) ds (loop (quotient n 2) (cons (modulo n 2)
ds)))))) (isqrt (lambda (n) (let loop ((x n) (y (quotient (+ n
1) 2))) (if (<= 0 (- y x) 1) x (loop y (quotient (+ y (quotient n
y)) 2)))))) (square? (lambda (n) (let ((n2 (isqrt n))) (= n (* n2
n2))))) (jacobi (lambda (a n) (let loop ((a a) (n n))
(cond ((= a 0) 0) ((= a 1) 1) ((= a 2) (case (modulo n 8)
((1 7) 1) ((3 5) -1))) ((even? a) (* (loop 2 n) (loop (/ a
2) n))) ((< n a) (loop (modulo a n) n)) ((and
(= (modulo a 4) 3) (= (modulo n 4) 3)) (- (loop n a)))
(else (loop n a)))))) (inverse (lambda (x m) (let loop ((a 1) (b
0) (g x) (u 0) (v 1) (w m)) (if (zero? w) (modulo a m)
(let ((q (quotient g w))) (loop u v w (- a (* q u)) (- b (* q
v)) (- g (* q w)))))))) (strong-pseudo-prime? (lambda (n a) (let
loop ((r 0) (s (- n 1))) (if (even? s) (loop (+ r 1) (/ s 2))
(if (= (expm a s n) 1) #t (let loop ((r r) (s s))
(cond ((zero? r) #f) ((= (expm a s n) (- n 1)) #t) (else
(loop (- r 1) (* s 2)))))))))) (chain (lambda (m f g u v) (let
loop ((ms (digits m)) (u u) (v v)) (cond ((null? ms) (values u
v)) ((zero? (car ms)) (loop (cdr ms) (f u) (g u v)))
(else (loop (cdr ms) (g u v) (f v))))))) (lucas-pseudo-prime? (lambda
(n) (let loop ((a 11) (b 7)) (let ((d (- (* a a) (* 4 b))))
(cond ((square? d) (loop (+ a 2) (+ b 1))) ((not (= (gcd
n (* 2 a b d)) 1)) (loop (+ a 2) (+ b 2))) (else (let*
((x1 (modulo (- (* a a (inverse b n)) 2) n))
(m (quotient (- n (jacobi d n)) 2)) (f
(lambda (u) (modulo (- (* u u) 2) n))) (g
(lambda (u v) (modulo (- (* u v) x1) n))))
(let-values (((xm xm1) (chain m f g 2 x1)))
(zero? (modulo (- (* x1 xm) (* 2 xm1)) n))))))))))) (if (not
(integer? n)) (error 'prime? "must be integer") (if (< n 2) #f (if
(even? n) (= n 2) (if (zero? (modulo n 3)) (= n 3) (and
(strong-pseudo-prime? n 2) (strong-pseudo-prime? n 3)
(lucas-pseudo-prime? n))))))))

--- In primenumbers@yahoogroups.com, "Aldrich" <aldrich617@...> wrote:
>
>
>
>
>
>
>
>
> --- In primenumbers@yahoogroups.com, Maximilian Hasler
maximilian.hasler@ wrote:
> >
> > Did you try
> >
> > > ?? ispseudoprime
> >
> > You should get something equivalent to
> >
http://pari.math.u-bordeaux.fr/dochtml/html/Arithmetic_functions.html#is\
pseudoprime
> >
>
> This is part of the information contained in the above reference:
>
> "If flag = 0, checks whether x is a
Baillie-Pomerance-Selfridge-Wagstaff pseudo prime (strong Rabin-Miller
pseudo prime for base 2, followed by strong Lucas test for the sequence
(P,-1), P smallest positive integer such that P^2 - 4 is not a square
mod x)".
>
> I am curious as to the nuts and bolts of applying these techniques.
> Are there pages of abstract complexities that need to be computed
> to get a result, or does the whole thing boil down to a few lines
> of code?
>
> Thanks a million, Max.
>
> Aldrich
>

[Non-text portions of this message have been removed]
• ... Well, its certainly a lot more calculation than simply recording a 1 or 2 as each prime candidate in a long chain appears. PARI can check primality of
Message 27 of 27 , Apr 22, 2011
--- In primenumbers@yahoogroups.com, "Phil" <philiplouisbewig@...> wrote:
>
> I discussed the Baillie-Wagstaff primality checker at my blog
> <http://programmingpraxis.com/2010/01/26/primality-checking-revisited/>
> . Here's the latest version of source code, in Scheme, which differs
> slightly from the original entry; it's more than "a few lines" of code,
> but not too long:
> (define (prime? n) (letrec ( (expm (lambda (b e m) (let ((times
> (lambda (x y) (modulo (* x y) m)))) (cond ((zero? e) 1) ((even?
> e) (expm (times b b) (/ e 2) m)) (else (times b (expm (times b b)
> (/ (- e 1) 2) m))))))) (digits (lambda (n) (let loop ((n n) (ds
> '())) (if (zero? n) ds (loop (quotient n 2) (cons (modulo n 2)
> ds)))))) (isqrt (lambda (n) (let loop ((x n) (y (quotient (+ n
> 1) 2))) (if (<= 0 (- y x) 1) x (loop y (quotient (+ y (quotient n
> y)) 2)))))) (square? (lambda (n) (let ((n2 (isqrt n))) (= n (* n2
> n2))))) (jacobi (lambda (a n) (let loop ((a a) (n n))
> (cond ((= a 0) 0) ((= a 1) 1) ((= a 2) (case (modulo n 8)
> ((1 7) 1) ((3 5) -1))) ((even? a) (* (loop 2 n) (loop (/ a
> 2) n))) ((< n a) (loop (modulo a n) n)) ((and
> (= (modulo a 4) 3) (= (modulo n 4) 3)) (- (loop n a)))
> (else (loop n a)))))) (inverse (lambda (x m) (let loop ((a 1) (b
> 0) (g x) (u 0) (v 1) (w m)) (if (zero? w) (modulo a m)
> (let ((q (quotient g w))) (loop u v w (- a (* q u)) (- b (* q
> v)) (- g (* q w)))))))) (strong-pseudo-prime? (lambda (n a) (let
> loop ((r 0) (s (- n 1))) (if (even? s) (loop (+ r 1) (/ s 2))
> (if (= (expm a s n) 1) #t (let loop ((r r) (s s))
> (cond ((zero? r) #f) ((= (expm a s n) (- n 1)) #t) (else
> (loop (- r 1) (* s 2)))))))))) (chain (lambda (m f g u v) (let
> loop ((ms (digits m)) (u u) (v v)) (cond ((null? ms) (values u
> v)) ((zero? (car ms)) (loop (cdr ms) (f u) (g u v)))
> (else (loop (cdr ms) (g u v) (f v))))))) (lucas-pseudo-prime? (lambda
> (n) (let loop ((a 11) (b 7)) (let ((d (- (* a a) (* 4 b))))
> (cond ((square? d) (loop (+ a 2) (+ b 1))) ((not (= (gcd
> n (* 2 a b d)) 1)) (loop (+ a 2) (+ b 2))) (else (let*
> ((x1 (modulo (- (* a a (inverse b n)) 2) n))
> (m (quotient (- n (jacobi d n)) 2)) (f
> (lambda (u) (modulo (- (* u u) 2) n))) (g
> (lambda (u v) (modulo (- (* u v) x1) n))))
> (let-values (((xm xm1) (chain m f g 2 x1)))
> (zero? (modulo (- (* x1 xm) (* 2 xm1)) n))))))))))) (if (not
> (integer? n)) (error 'prime? "must be integer") (if (< n 2) #f (if
> (even? n) (= n 2) (if (zero? (modulo n 3)) (= n 3) (and
> (strong-pseudo-prime? n 2) (strong-pseudo-prime? n 3)
> (lucas-pseudo-prime? n))))))))
>
>

Well, its certainly a lot more calculation than simply recording
a '1' or '2' as each prime candidate in a long chain appears.
PARI can check primality of 19-20 digit integers at a rate of
about 8000/sec, according to Maximillian, so I would expect
Praxis to be a bit slower. My primitive pm2 hit 11500/sec when
I put it into a Lazarus FreePascal compiler on a Pentium4, so I
feel it has potential. I would have to seriously upgrade my
programming skills to see how far the idea can really go
however. Somebody please shoot it down - my brain hurts!
Its pretty easy to check out even if Pascal is not your bag.