## p-SPRP

Expand Messages
• Hello all, I have made small researches for page. Strong PRPs http://www.utm.edu//research/primes/prove/prove2_3.html I checked only two bases what to detect
Message 1 of 12 , Sep 1, 2002
Hello all,

I have made small researches for page.
Strong PRPs
http://www.utm.edu//research/primes/prove/prove2_3.html

I checked only two bases what to detect the best values for "Combining these
tests to prove primality".

Chris Caldwell write:
> If n < 9,080,191 is a both 31 and 73-SPRP, then n is prime.

checked a1<109, a2< 7919 and other values are retrieved:
If n < 9,254,521 is a both 103 and 6871-SPRP, then n is prime.
If n < 9,863,461 is a both 17 and 6661-SPRP, then n is prime.
and best
If n < 18,985,627 is a both 31 and 1171 -SPRP, then n is prime.

Who more densely researched Combining tests for 2,3,4 ... values? More than
it is known on page Chris.
You see the knowledge of these numbers has practical value and to success
competes with the sieve of Eratosthenes with small numbers, for the daily
tests, because not enough memory requires.

Leonid Durman
• ... Excellent! Maybe you could send this to Richard Pinch, via email address at http://www.chalcedon.demon.co.uk/rgep.html and tempt him into to spare-time
Message 2 of 12 , Sep 1, 2002
Leonid Durman wrote:
> If n < 18,985,627 is a both
> 31 and 1171 -SPRP, then n is prime.
Excellent!
Maybe you could send this to Richard Pinch, via
http://www.chalcedon.demon.co.uk/rgep.html
and tempt him into to spare-time pseudoprime
hunting?
David
• ... Great work, Leonid. I briefly looked at this problem in the past, but I restricted myself to a smaller set of bases, and discovered that I was almost
Message 3 of 12 , Sep 1, 2002
--- Leonid Durman <durman@...> wrote:
> Hello all,
>
> I have made small researches for page.
> Strong PRPs
> http://www.utm.edu//research/primes/prove/prove2_3.html
>
> I checked only two bases what to detect the best values for "Combining these
> tests to prove primality".
>
> Chris Caldwell write:
> > If n < 9,080,191 is a both 31 and 73-SPRP, then n is prime.
>
> checked a1<109, a2< 7919 and other values are retrieved:
> If n < 9,254,521 is a both 103 and 6871-SPRP, then n is prime.
> If n < 9,863,461 is a both 17 and 6661-SPRP, then n is prime.
> and best
> If n < 18,985,627 is a both 31 and 1171 -SPRP, then n is prime.
>
> Who more densely researched Combining tests for 2,3,4 ... values? More than
> it is known on page Chris.
> You see the knowledge of these numbers has practical value and to success
> competes with the sieve of Eratosthenes with small numbers, for the daily
> tests, because not enough memory requires.

Great work, Leonid.
I briefly looked at this problem in the past, but I restricted myself to a
smaller set of bases, and discovered that I was almost certainly just

Am I right in thinking that your a1/a2 distinction was to first find a1-SPSPs
for all a1 in range, and then only check a2-SPSP-ness for this restricted
set of candidates?

This looks like it's screaming for some distributed computing effort...
With a massively parallel modular multiplier/exponentiator such as Jim's or David's
from their GFNSieve, it might be possible to push this a lot further.
I'd happily stick my PPro/200 on this 24/7 for many a month, as it's doing
nothing else presently (I know - it's a crime against primality).
It looks like it can be distributed easily, as it's can be turned into a
2D-task (which means it's easy to make sure people don't tread on each
other's toes, and can still run as long as they want).

Phil

=====
"The hottest places in Hell are reserved for those who, in
times of moral crisis, preserved their neutrality."
-- John F. Kennedy, 24 June 1963, claiming to quote Dante,
to whom this has been incorrectly attributed ever since.

__________________________________________________
Do You Yahoo!?
Yahoo! Finance - Get real-time stock quotes
http://finance.yahoo.com
• ... some more examples for composite bases remember to check gcd(n,base)=1 bases 2 & 1226150 and n
Message 4 of 12 , Sep 1, 2002
On Sunday 01 Sep 2002 11:46 pm, Phil Carmody wrote:
> --- Leonid Durman <durman@...> wrote:
> > Hello all,
> >
> > I have made small researches for page.
> > Strong PRPs
> > http://www.utm.edu//research/primes/prove/prove2_3.html
> >
> > I checked only two bases what to detect the best values for "Combining
> > these tests to prove primality".
> >
> > Chris Caldwell write:
> > > If n < 9,080,191 is a both 31 and 73-SPRP, then n is prime.
> >
> > checked a1<109, a2< 7919 and other values are retrieved:
> > If n < 9,254,521 is a both 103 and 6871-SPRP, then n is prime.
> > If n < 9,863,461 is a both 17 and 6661-SPRP, then n is prime.
> > and best
> > If n < 18,985,627 is a both 31 and 1171 -SPRP, then n is prime.
> >

some more examples

for composite bases remember to check gcd(n,base)=1
bases
2 & 1226150 and n<38,210323 then n is prime
2 & 305185 and n<72,498253 and sqrt condition then n is prime
2 & 1121 & 6165 and n<20689,557337
2 & 463 & 735 & 849 and n<5,486664,348901 then n is prime

sqrt condition is checking that square root of -1 mod n are the same for all
bases , this comes for "free" in the SPRP test ( we only test it if it is
easy to find)

> > Who more densely researched Combining tests for 2,3,4 ... values? More
> > than it is known on page Chris.
> > You see the knowledge of these numbers has practical value and to success
> > competes with the sieve of Eratosthenes with small numbers, for the daily
> > tests, because not enough memory requires.
>
> Great work, Leonid.
> I briefly looked at this problem in the past, but I restricted myself to a
> smaller set of bases, and discovered that I was almost certainly just
>
> Am I right in thinking that your a1/a2 distinction was to first find
> a1-SPSPs for all a1 in range, and then only check a2-SPSP-ness for this
> restricted set of candidates?
>
> This looks like it's screaming for some distributed computing effort...
> With a massively parallel modular multiplier/exponentiator such as Jim's or
> David's from their GFNSieve, it might be possible to push this a lot
> further. I'd happily stick my PPro/200 on this 24/7 for many a month, as
> it's doing nothing else presently (I know - it's a crime against
> primality).

for finding SPRP's for a fixed set of bases it is best NOT to use any powering
at all , I can dig out some referances if your interested , they use a
backtracking search .

> It looks like it can be distributed easily, as it's can be turned into a
> 2D-task (which means it's easy to make sure people don't tread on each
> other's toes, and can still run as long as they want).
>

It is easy to distribute , although note my code is not optimal , and
temporary disabled (internet troubles..again..)

http://217.35.81.229/dist.html

jason

>
> Phil
>
>
> =====
> "The hottest places in Hell are reserved for those who, in
> times of moral crisis, preserved their neutrality."
> -- John F. Kennedy, 24 June 1963, claiming to quote Dante,
> to whom this has been incorrectly attributed ever since.
>
> __________________________________________________
> Do You Yahoo!?
> Yahoo! Finance - Get real-time stock quotes
> http://finance.yahoo.com
>
>
> Unsubscribe by an email to: primenumbers-unsubscribe@egroups.com
> The Prime Pages : http://www.primepages.org
>
>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
• Hello all, ... It still best practical results. I have spent only hour for search. But at the large expenditures of time and resources it is possible to
Message 5 of 12 , Sep 1, 2002
Hello all,

Jason wrote:
>for composite bases remember to check gcd(n,base)=1
>bases
>2 & 1226150 and n<38,210323 then n is prime
>2 & 305185 and n<72,498253 and sqrt condition then n is prime
>2 & 1121 & 6165 and n<20689,557337
>2 & 463 & 735 & 849 and n<5,486664,348901 then n is prime

It still best practical results.
I have spent only hour for search. But at the large expenditures of time and
resources it is possible to discover the best values.
Excellent work.

>for finding SPRP's for a fixed set of bases it is best NOT to use any
powering
>at all , I can dig out some referances if your interested , they use a
>backtracking search .

Yes, certainly. I am interested in any information which can to help,
and I plan to create the high-performance code on an assembler.
I would be interested to discover the best outcomes for values n<2^64. The
sieve here is already less effective, a lot of memory permanently requires
even if to optimize. And for practical researches with prime, SPRP test
would be useful.

Regards

Leonid Durman
• ... You basically mean remember the last-but-one value in the SPRP test. ... If you could get those references I d be grateful. I don t know exactly what you
Message 6 of 12 , Sep 2, 2002
--- Jason Moxham <j.l.moxham@...> wrote:
> for composite bases remember to check gcd(n,base)=1
> bases
> 2 & 1226150 and n<38,210323 then n is prime
> 2 & 305185 and n<72,498253 and sqrt condition then n is prime
> 2 & 1121 & 6165 and n<20689,557337
> 2 & 463 & 735 & 849 and n<5,486664,348901 then n is prime
>
> sqrt condition is checking that square root of -1 mod n are the same for all
> bases , this comes for "free" in the SPRP test ( we only test it if it is
> easy to find)

You basically mean remember the last-but-one value in the SPRP test.

> > > Who more densely researched Combining tests for 2,3,4 ... values? More
> > > than it is known on page Chris.
> > > You see the knowledge of these numbers has practical value and to success
> > > competes with the sieve of Eratosthenes with small numbers, for the daily
> > > tests, because not enough memory requires.
> >
> > Great work, Leonid.
> > I briefly looked at this problem in the past, but I restricted myself to a
> > smaller set of bases, and discovered that I was almost certainly just
> >
> > Am I right in thinking that your a1/a2 distinction was to first find
> > a1-SPSPs for all a1 in range, and then only check a2-SPSP-ness for this
> > restricted set of candidates?
> >
> > This looks like it's screaming for some distributed computing effort...
> > With a massively parallel modular multiplier/exponentiator such as Jim's or
> > David's from their GFNSieve, it might be possible to push this a lot
> > further. I'd happily stick my PPro/200 on this 24/7 for many a month, as
> > it's doing nothing else presently (I know - it's a crime against
> > primality).
>
> for finding SPRP's for a fixed set of bases it is best NOT to use any powering
> at all , I can dig out some referances if your interested , they use a
> backtracking search .

If you could get those references I'd be grateful.

I don't know exactly what you mean by a backtracking search, but last night
I thought about possible ways to approach this, and many ideas I came up
with didn't involve performing SPRP tests. Some involved trial-dividing
a few thousand large numers for small factors, others involved taking
discrete logarthms modulo small bases (where small= half the size of the
composites we'd be searching). In fact I was completely bamboozled by the
number of different approaches to this problem that I could come up with.

> > It looks like it can be distributed easily, as it's can be turned into a
> > 2D-task (which means it's easy to make sure people don't tread on each
> > other's toes, and can still run as long as they want).
>
> It is easy to distribute , although note my code is not optimal , and
> temporary disabled (internet troubles..again..)
>
> http://217.35.81.229/dist.html

You can always upload stuff like this to the files area of the yahoogroup.
Just create a folder for it to keep things neat.

Phil

=====
"The hottest places in Hell are reserved for those who, in
times of moral crisis, preserved their neutrality."
-- John F. Kennedy, 24 June 1963, claiming to quote Dante,
to whom this has been incorrectly attributed ever since.

__________________________________________________
Do You Yahoo!?
Yahoo! Finance - Get real-time stock quotes
http://finance.yahoo.com
• I see that Jason used 2 & x & y ... That makes the problem rather easy up to n=10^13, since one can pinch the file
Message 7 of 12 , Sep 2, 2002
I see that Jason used 2 & x & y ...
That makes the problem rather easy up to
n=10^13, since one can pinch the file
http://www.chalcedon.demon.co.uk/rgep/spsp-13.gz
How about up to 10^14 Jason :-)
David
• ... Wipe that smilie off your post, David. Jason has all 2 SPSPs up to 4,503,586,330,870,201 Pinch is _such_ a 20th century resource... Phil ===== The hottest
Message 8 of 12 , Sep 2, 2002
> I see that Jason used 2 & x & y ...
> That makes the problem rather easy up to
> n=10^13, since one can pinch the file
> http://www.chalcedon.demon.co.uk/rgep/spsp-13.gz
> How about up to 10^14 Jason :-)

Wipe that smilie off your post, David.
Jason has all 2 SPSPs up to 4,503,586,330,870,201
Pinch is _such_ a 20th century resource...

Phil

=====
"The hottest places in Hell are reserved for those who, in
times of moral crisis, preserved their neutrality."
-- John F. Kennedy, 24 June 1963, claiming to quote Dante,
to whom this has been incorrectly attributed ever since.

__________________________________________________
Do You Yahoo!?
Yahoo! Finance - Get real-time stock quotes
http://finance.yahoo.com
• ... But the smilie was written _after_ studying http://217.35.81.229/spp.html so what joke is on whom, Phil? David (whose humour[?] is known to be perverse)
Message 9 of 12 , Sep 2, 2002
I wrote:
> How about up to 10^14 Jason :-)
Phil quipped:
> Wipe that smilie off your post, David.
But the smilie was written _after_ studying
http://217.35.81.229/spp.html
so what joke is on whom, Phil?
David (whose humour[?] is known to be perverse)
• ... I ve never liked slapstick. Phil ===== The hottest places in Hell are reserved for those who, in times of moral crisis, preserved their neutrality. --
Message 10 of 12 , Sep 2, 2002
> I wrote:
> > How about up to 10^14 Jason :-)
> Phil quipped:
> > Wipe that smilie off your post, David.
> But the smilie was written _after_ studying
> http://217.35.81.229/spp.html
> so what joke is on whom, Phil?
> David (whose humour[?] is known to be perverse)

I've never liked slapstick.

Phil

=====
"The hottest places in Hell are reserved for those who, in
times of moral crisis, preserved their neutrality."
-- John F. Kennedy, 24 June 1963, claiming to quote Dante,
to whom this has been incorrectly attributed ever since.

__________________________________________________
Do You Yahoo!?
Yahoo! Finance - Get real-time stock quotes
http://finance.yahoo.com
• ... This is what my current code is based on http://www.chalcedon.demon.co.uk/publish.html#41 Not read this yet , but it looks good
Message 11 of 12 , Sep 2, 2002
On Monday 02 Sep 2002 7:49 am, Leonid Durman wrote:
> Hello all,
>
> Jason wrote:
> >for composite bases remember to check gcd(n,base)=1
> >bases
> >2 & 1226150 and n<38,210323 then n is prime
> >2 & 305185 and n<72,498253 and sqrt condition then n is prime
> >2 & 1121 & 6165 and n<20689,557337
> >2 & 463 & 735 & 849 and n<5,486664,348901 then n is prime
>
> It still best practical results.
> I have spent only hour for search. But at the large expenditures of time
> and resources it is possible to discover the best values.
> Excellent work.
>
> >for finding SPRP's for a fixed set of bases it is best NOT to use any
>
> powering
>
> >at all , I can dig out some referances if your interested , they use a
> >backtracking search .
>
> Yes, certainly. I am interested in any information which can to help,
> and I plan to create the high-performance code on an assembler.
> I would be interested to discover the best outcomes for values n<2^64. The
> sieve here is already less effective, a lot of memory permanently requires
> even if to optimize. And for practical researches with prime, SPRP test
> would be useful.

This is what my current code is based on
http://www.chalcedon.demon.co.uk/publish.html#41

Not read this yet , but it looks good
http://www.bell-labs.com/user/bleichen/diss/thesis.html

Jason

>
> Regards
>
> Leonid Durman
• ... Well not quite , they have yet to be verifyed 4.5e15=4,503,586,330,870,201=2^52 do have nearly all up to 2^56=7.2e16 , again not verified , missing the
Message 12 of 12 , Sep 2, 2002
On Monday 02 Sep 2002 11:07 am, Phil Carmody wrote:
> > I see that Jason used 2 & x & y ...
> > That makes the problem rather easy up to
> > n=10^13, since one can pinch the file
> > http://www.chalcedon.demon.co.uk/rgep/spsp-13.gz
> > How about up to 10^14 Jason :-)
>
> Wipe that smilie off your post, David.
> Jason has all 2 SPSPs up to 4,503,586,330,870,201

Well not quite , they have yet to be verifyed
4.5e15=4,503,586,330,870,201=2^52

do have nearly all up to 2^56=7.2e16 , again not verified , missing the
squares , and split up up into many inconvient files...

> Pinch is _such_ a 20th century resource...

I glad to offer 21st century resources , note: coming soon 22nd century
resources and more....

jason

>
> Phil
>
>
> =====
> "The hottest places in Hell are reserved for those who, in
> times of moral crisis, preserved their neutrality."
> -- John F. Kennedy, 24 June 1963, claiming to quote Dante,
> to whom this has been incorrectly attributed ever since.
>
> __________________________________________________
> Do You Yahoo!?
> Yahoo! Finance - Get real-time stock quotes
> http://finance.yahoo.com
>
>
> Unsubscribe by an email to: primenumbers-unsubscribe@egroups.com
> The Prime Pages : http://www.primepages.org
>
>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
Your message has been successfully submitted and would be delivered to recipients shortly.