Re: p-SPRP

Expand Messages
• 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 1 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 2 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 3 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 4 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 5 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 6 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 7 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 8 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.