Request from Phil

[fatphil]

Originally Posted by masser

Does anyone know if the residues from PRP match the residues of LLR?


Via phrot with b = 3:

254*5^474558-1 [-316717,355923,344018,772502] is composite LLR64=34691A2F4DA6F620. (t=9989.12s)

Via PRP:

254*5^474558-1 is not prime. RES64: EF65F8011E5542EE. OLD64: FBE69A2253DBFA1A

Could someone test this number with LLR?

At *that* size, there's probably been FFT roundoff errors, and that's line noise. Can you run with -a1 (or -a2...) to force the limb size to be 5^8 rather than 5^9? Unfortunately, maxerr checking it quite expensive, so you will notice it slow down when I put it in. (Though perhaps I could limit it to only the most likely limbs?)

Phil

[fatphil]

Originally Posted by fatphil

At *that* size, there's probably been FFT roundoff errors, and that's line noise. Can you run with -a1 (or -a2...) to force the limb size to be 5^8 rather than 5^9? Unfortunately, maxerr checking it quite expensive, so you will notice it slow down when I put it in. (Though perhaps I could limit it to only the most likely limbs?)

I'm running -a1 myself. Results after a night's sleep...

[axn]

Originally Posted by masser

Does anyone know if the residues from PRP match the residues of LLR?

Yes. LLR internally uses GW's PRP routines only (hence the "Please credit GW's PRP" line when it finds a probable prime). The residue matches RES64, not OLD64 (which is there for compatibility with older version of PRP).

[fatphil]

Originally Posted by masser

254*5^474558-1 is not prime. RES64: EF65F8011E5542EE. OLD64: FBE69A2253DBFA1A

$ ./phrot.cygp3 -b3 -a1 -q '254*5^474558-1'
Actually testing 3968750*390625^59319-1 (59321/131072 limbs)
254*5^474558-1 [-121107,-115114,171815,113968] is composite LLR64=EF65F8011E5542EE. (t=21392.67s)

So Phrot is capable of testing the number correctly, it just needs the -a switch at that size.

So, I need to either:
a) programattically predict if a test has a > epsilon chance of FFT roundoff error, and ensure that a smaller limb size is chosen (will slow down some tests)
b) keep tabs on the roundoff errors (slows down all tests).
c) both.

(c) is the long term choice, obviously.

[axn]

I tested this with -a2 switch. Doesn't seem to have made any difference for the FFT size. Residues are matching

phrot.46.exe -a2 -b=3 -q"254*5^474558-1"
Actually testing 3968750*390625^59319-1 (59321/131072 limbs)
254*5^474558-1 [-121107,-115114,171815,113968] is composite LLR64=EF65F8011E5542EE. (t=16961.28s)

[fatphil]

Originally Posted by axn1

I tested this with -a2 switch. Doesn't seem to have made any difference for the FFT size. Residues are matching

phrot.46.exe -a2 -b=3 -q"254*5^474558-1"
Actually testing 3968750*390625^59319-1 (59321/131072 limbs)
254*5^474558-1 [-121107,-115114,171815,113968] is composite LLR64=EF65F8011E5542EE. (t=16961.28s)

390625 is vastly smaller than 1953125. I'd be surprised if it chose a smaller base even if you cranked it up to -a7. 390625 will cope with numbers 25 times larger than 1953125.

[fatphil]

Originally Posted by fatphil

At *that* size, there's probably been FFT roundoff errors, and that's line noise. Can you run with -a1 (or -a2...) to force the limb size to be 5^8 rather than 5^9? Unfortunately, maxerr checking it quite expensive, so you will notice it slow down when I put it in. (Though perhaps I could limit it to only the most likely limbs?)

Phil

sh-3.1$ ./phrot.cygp3 -b=3 -q "254*5^474558-1"
Actually testing 3968750*1953125^52728-1 (52730/114688 limbs)
i=2 err=0.00000
i=3 err=0.00000
i=4 err=0.00000
i=5 err=0.00002
i=6 err=0.00006
i=7 err=0.00028
i=8 err=0.00038
i=9 err=0.00074
i=10 err=0.00223
i=11 err=0.00393
i=12 err=0.00533
i=13 err=0.01116
i=14 err=0.01562
i=15 err=0.02232
i=16 err=0.03001
i=17 err=0.07143
i=18 err=0.10163
i=19 err=0.16785
i=20 err=0.25000
i=21 err=0.32141
i=24 err=0.35715
i=29 err=0.40472
i=58 err=0.40665
i=119 err=0.40829
i=210 err=0.42856
i=2062 err=0.46428

I'm pretty sure it's gone bang if it's that close to 0.5 after only a few thousand iterations. I reckon that this number wasn't horribly into the "5^9 is too big a limb" territory. It would be good to grab some maxerr figures for intermediate sizes. That will permit me to more intelligently select limb sizes robomatically within the code. I'll upload a slightly less verbose P3 binary later this evening.

[masser]

We should also test the top ten primes found by the Riesel search:

175268*5^360870-1
339728*5^249588-1
74528*5^218272-1
346078*5^176421-1
201590*5^165080-1
256568*5^160920-1
217592*5^157128-1
294704*5^149576-1
292414*5^148601-1
197774*5^147396-1

Has this been done yet?

[fatphil]

Originally Posted by masser

We should also test the top ten primes found by the Riesel search:

175268*5^360870-1
339728*5^249588-1
74528*5^218272-1
346078*5^176421-1
201590*5^165080-1
256568*5^160920-1
217592*5^157128-1
294704*5^149576-1
292414*5^148601-1
197774*5^147396-1

Has this been done yet?

That would be a very good stress test for the code I'll be uploading in about 4 hours. I'd say that it's probably lower priority for me than the information-gathering from running across loads of smaller ones (I'll be doing that later - up to n=10000, say). However, it's now sauna time, so my last few hacks will need to wait for a couple of hours.

Phil

[tnerual]

Originally Posted by masser

We should also test the top ten primes found by the Riesel search:

175268*5^360870-1
339728*5^249588-1
74528*5^218272-1
346078*5^176421-1
201590*5^165080-1
256568*5^160920-1
217592*5^157128-1
294704*5^149576-1
292414*5^148601-1
197774*5^147396-1

Has this been done yet?

74528*5^218272-1 reserved tnerual

175268*5^360870-1 free to test
339728*5^249588-1 free to test
346078*5^176421-1 free to test
201590*5^165080-1 free to test
256568*5^160920-1 free to test
217592*5^157128-1 free to test
294704*5^149576-1 free to test
292414*5^148601-1 free to test
197774*5^147396-1 free to test

[fatphil]

Originally Posted by tnerual

74528*5^218272-1 reserved tnerual

175268*5^360870-1 free to test
339728*5^249588-1 free to test
346078*5^176421-1 free to test
201590*5^165080-1 free to test
256568*5^160920-1 free to test
217592*5^157128-1 free to test
294704*5^149576-1 free to test
292414*5^148601-1 free to test
197774*5^147396-1 free to test

I've actually tested most of them with an old version of the code already!
The small ones all passed, the largest failed, I forget about the second largest.
I've not changed the modular exponentiator or modular reduction algorithms significantly since then. So the results should be identical.

However, the new information that would be very useful would be the new maxerrs info, and some auxiliary info that won't mean anything to anyone else, but will help me tremendously.

So here's 0.47...