Request from Phil

[axn]

put the number between "":

phrot -q "285728*5^411274-1"

[axn]

Originally Posted by fatphil

If you can tell me unambiguously what a LLR residue represents, then I will look into trying to mimic it.

Base 3 PRP test with last 64 bits of the result written as 16 character hex string.

Some samples for your testing:
164852*5^100524-1 RES64: A850C2F3D5ABB57E
252872*5^100524-1 RES64: 0EB3F09D33962912

[fatphil]

Originally Posted by tnerual

i tried it just to see the speed difference.

i got some problem.
first: i had to rename it as a .exe file (in my case phrot.exe) to get it running. (easy to solve)
second: i had to download the cygwin1.dll (easy to solve)

third: when trying to run it i got this output:

phrot -q 285728*5^411274-1
Error: base out of range
285728*5^411274-1
^ near here

i'm using a centrino 1.4 with win xp supposed to be the same architecture as a p3.
can someone help me ?

I recommend running it from within a Cygwin window rather than a DOS window. All that matters to cygwin is the executable bit, not the last four characters of the filename (viz. ".exe").

I suspect the final problem will go away too in a cygwin window. Sticking anything that contains '$', '*', or '^' in single quotes is always a good precaution.

FatPhil

[fatphil]

Originally Posted by axn1

Base 3 PRP test with last 64 bits of the result written as 16 character hex string.

Some samples for your testing:
164852*5^100524-1 RES64: A850C2F3D5ABB57E
252872*5^100524-1 RES64: 0EB3F09D33962912

I currently use base 2. Using base 3 will decrease the usable range of k slightly on x86 platforms. And I presume that's a normal Fermat PRP test, 3^(n-1), not a Euler one 3^((n-1)/2).

It's not entirely trivial. We'll see what transpires...

Phil

[axn]

Originally Posted by fatphil

I currently use base 2. Using base 3 will decrease the usable range of k slightly on x86 platforms. And I presume that's a normal Fermat PRP test, 3^(n-1), not a Euler one 3^((n-1)/2).

How much would the k range suffer if base 3 is used? Also will the FFT break happen earlier for a given k?

Yes, it is a regular PRP test.

Some preliminary results:

phrot.cygp3.exe -q "164852*5^100524-1"
Actually testing 20606500*1953125^11169-1 (11171/24576 limbs)
164852*5^100524-1 [798766,-273453,133316,695627] is composite. (t=451.46s)

phrot.cygp3.exe -q "119098*5^130509-1"
Actually testing 119098*1953125^14501-1 (14502/32768 limbs)
119098*5^130509-1 [517504,242017,399396,-286254] is composite. (t=765.21s)

As opposed to LLR:

LLR tests only k*2^n±1 numbers, so, we will do a PRP test of 164852*5^100524-1
164852*5^100524-1 is not prime.  RES64: A850C2F3D5ABB57E  Time: 1082.993 sec.

LLR tests only k*2^n±1 numbers, so, we will do a PRP test of 119098*5^130509-1
119098*5^130509-1 is not prime.  RES64: D1A84329ACA14FB6  Time: 1696.001 sec.

About 2x speedup!

[tnerual]

Originally Posted by axn1

put the number between "":

phrot -q "285728*5^411274-1"

it do the job in a "dos window"

thanks.

[michaf]

Out of curiosity:
for numbers of size +- 2^100000

phrot takes 64 seconds and PRP3.1.0 takes 24.
Thats on an athlon 64 X2 3800+

Just couldn't resist

[fatphil]

Originally Posted by michaf

Out of curiosity:
for numbers of size +- 2^100000

phrot takes 64 seconds and PRP3.1.0 takes 24.
Thats on an athlon 64 X2 3800+

Just couldn't resist

I presume that's not just _size_ 2^100000, but of _form_ k*2^100000+/-1.
That's basically LLR/PRP/PFGW's sweet spot - absolutely no point in running Phrot for those forms on an x86 machine. That and GW's SSE2 convoluions work, and YEAFFT's don't, so I have to stick with 8 plain old FPU registers.

This is the 'base 5' project, after all, so it matters not.

[tnerual]

impressive :
llrnet:
285728*5^411274-1 is not prime. RES64: 5C1971CB15E8C2BE Time: 31575.377 sec.
phrot...
285728*5^411274-1 [-872160,-901141,235457,-385997] is composite. (t=11274.15s) :surprised

this with high exponent, on a centrino 1400 with win XP

[fatphil]

Originally Posted by tnerual

impressive :
llrnet:
285728*5^411274-1 is not prime. RES64: 5C1971CB15E8C2BE Time: 31575.377 sec.
phrot...
285728*5^411274-1 [-872160,-901141,235457,-385997] is composite. (t=11274.15s) :surprised

this with high exponent, on a centrino 1400 with win XP

For reference, I'd rather you verified known primes rather than composites. Until I can reproduce the LLR residue, composite results don't prove that the calculation has worked OK. PRPs do. I've never _ever_ tested it on a number that large (heck, my development machine is a PentiumIII/800), so have no idea if there are roundoff issues with exponents that high. I don't have maxerr checking yet, so the above *might* be complete garbage.

[tnerual]

Originally Posted by fatphil

For reference, I'd rather you verified known primes rather than composites. Until I can reproduce the LLR residue, composite results don't prove that the calculation has worked OK. PRPs do. I've never _ever_ tested it on a number that large (heck, my development machine is a PentiumIII/800), so have no idea if there are roundoff issues with exponents that high. I don't have maxerr checking yet, so the above *might* be complete garbage.

i tested it because it was the biggest i have tested with llr on this computer ... now it's running llrnet again ... and as soon as i find a prime (minimum top200 if i find one), i will test it again with phrot.and it was more for speed comparison than to prove that the app is ok