--- 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

> > treading over ground covered by Jaeschke already.

> >

> > 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