Factoring database - Page 142

ATH · 2017-02-16, 12:53

At 31 digits there is very far between any SPRP, so the average number at 31 digits probably fails very close to 0 times.

http://mathworld.wolfram.com/StrongPseudoprime.html

Quote:

A composite number is a strong pseudoprime to at most 1/4 of all bases less than itself (Monier 1980, Rabin 1980).

So this number is actually above 1/4 up to 100,000, but if we ran all bases up to n it would probably end up with a very low percentage.

Edit: At 100,000,000 it is still above 1/4 actually, that is surprising: 25,003,138 fails.

paulunderwood · 2017-02-16, 13:23

Quote:

Originally Posted by ATH

Testing for fun which bases n=1396981702787004809899378463251 fails for:

Between bases 2 and 1000: 265 of them fails. Base 2 actually does not fail, so GMP does not use base 2 apparantly.

These bases<1000 shows n as PRP:

Code:

3 9 16 17 19 20 22 25 27 31 41 43 46 48 51 53 56 57 58 60 61 66 70 75 77 81 83 93 101 103 104 113 118 123 129 130 138 139 143 144 153 157 159 161 163 168 171 174 180 183 188 193 196 198 203 210 225 227 229 231 235 239 243 245 249 254 256 262 268 271 272 277 279 281 289 292 296 299 302 303 304 309 312 316 317 320 323 334 335 339 340 347 352 354 361 362 364 365 369 370 373 374 377 380 382 387 388 390 395 398 400 407 413 414 417 418 421 425 428 429 431 432 433 440 446 455 459 461 463 466 471 475 477 483 484 485 487 489 491 496 499 500 502 504 509 513 522 523 527 535 540 547 548 549 550 557 564 568 577 579 588 589 594 596 601 605 609 620 622 625 630 656 658 674 675 676 681 682 685 686 687 688 693 697 698 705 710 712 716 717 719 727 729 731 734 735 736 745 747 751 757 762 767 768 775 778 779 781 782 786 787 797 802 804 809 813 816 817 820 821 831 837 843 845 848 851 859 860 867 872 874 876 886 888 889 890 895 896 897 898 901 902 906 909 912 914 917 920 927 928 936 938 941 946 947 948 951 952 960 961 969 976 979 983 986

2-10000: 2559 bases fails

2-100000: 25017 bases fails

Why run lots of Miller-Rabin rounds when (strong) Fermat + carefully chosen (strong) Lucas has never known to fail and costs in total 3 or 4 MR -- and if you find a counterexample you get $620?

danaj · 2017-02-16, 14:34

GMP does a little trial division, a base 210 Fermat test, then n Miller-Rabin tests, using identically-seeded pseudorandom bases. It gives a deterministic test which is good for consistency, testing, and debugging, but also allows one to find pseudoprimes, albeit not as easily as the old "first n prime bases" methods like libtommath still uses.

Nicely wrote about this over a decade ago: GNU GMP mpz_probab_prime_p pseudoprimes.

I'm not really sure why the base 210 Fermat test is added, as it doesn't really take any less time than a full M-R test as is done right before the M-R tests start. The Euler-Plumb test at least costs ~5% less time and is stronger than the Fermat test, so would make a better pre-test IMO.

Far better is, as Paul has said a few times, to switch to BPSW. WraithX offered his code a few years ago on one of the GMP mailing lists but it wasn't taken. I should tidy up my code and do the same since it's faster. It is deterministic and has no known counterexamples (even when the test is weakened to make them easier to find). The time taken is comparable to using an argument of 2-3 for mpz_probab_prime_p.

R. Gerbicz · 2017-02-16, 19:23

Quote:

Originally Posted by chris2be8

That explains why the following code from factMsieve.pl said a lot of small numbers in factordb are prime when they are really composite.

I'm uploading the factorizations also, all of my submitted probable primes had the form of n=p*q for q=2*p-1.

Quote:

Originally Posted by ATH

Testing for fun which bases n=1396981702787004809899378463251 fails for:

Between bases 2 and 1000: 265 of them fails. Base 2 actually does not fail, so GMP does not use base 2 apparantly.

For Miller-Rabin gmp doesn't use fixed base! But and it is important in my search is that for a given interval of n it is using the same set of base for the first T tests (if you increase T then the interval will be smaller). Here the bases are large, "close" to n, so the Arnault's attack is just not working to get n that is a strong pseudo prime for many bases.

CRGreathouse · 2017-02-17, 06:23

Quote:

Originally Posted by danaj

Far better is, as Paul has said a few times, to switch to BPSW.

Yes. Depending on what you're trying to do a random Miller-Rabin first to more quickly weed out composites might be worthwhile, but after that I certainly wouldn't suggest anything weaker than BPSW. We've come a long way since 1980.

MisterBitcoin · 2018-02-01, 16:49

Does anyone know how to PRP test an cofactor from an Fibonacci Number?
Looks like pfgw doens´t like this type of numbers.

ATH · 2018-02-01, 19:32

You can always output the entire decimal cofactor to a file and pfgw will read that. How big numbers are you working with?

MisterBitcoin · 2018-02-01, 19:52

Quote:

Originally Posted by ATH

You can always output the entire decimal cofactor to a file and pfgw will read that. How big numbers are you working with?

I recently found an Fibanocci number cofactor in factorDB U-list and tryed to make an PRP test which failed.
Was about 21K digits, or so.
I´ll give it a try, maybe I´ll find some small factors with ECM. Thanks, anyway.

ATH · 2018-02-01, 20:47

21K is nothing I have done at least 750K digits by just writing the entire number to a text file and then running pfgw:
pfgw64.exe -f0 -V -l number.txt

-f0 for no factoring assuming you did factoring earlier, -V for verbose if you want that, and -l to log results in the "pfgw.out" file or -l<logfilename>.
Use -b<base> to run PRP test in another base than 3, like -b2, -b5, -b7 etc. up to -b255.

axn · 2018-02-02, 02:37

Quote:

Originally Posted by MisterBitcoin

I recently found an Fibanocci number cofactor in factorDB U-list and tryed to make an PRP test which failed.
Was about 21K digits, or so.
I´ll give it a try, maybe I´ll find some small factors with ECM. Thanks, anyway.

At 21K, factordb will itself do it for you, if you ask it nicely.

MisterBitcoin · 2018-03-29, 08:37

I just fullyfactored my first number above 100 digits. (I mean a odd number, no just somethink like 10^n*3) It has 240 digits. Here.

Found 3 factors (P18, P20 and P28). Remaining cofactor was prime.

Next one, this time P220 cofactor. New personal record.

Next edit:
Two more FF, we should need table at the status that shows us the amount of fully-factored composite numbers. Please.

2018-03-29, 08:37	#1562
MisterBitcoin "Nuri, the dragon :P" Jul 2016 Good old Germany 1100101001₂ Posts	I just fullyfactored my first number above 100 digits. (I mean a odd number, no just somethink like 10^n3) It has 240 digits. Here. Found 3 factors (P18, P20 and P28). Remaining cofactor was prime. Next one, this time P220 cofactor. New personal record. Next edit: Two more FF, we should need table at the status that shows us the amount of fully-factored composite numbers. Please. Last fiddled with by MisterBitcoin on 2018-03-29 at 09:20*

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Database for k-b-b's:	3.14159	Miscellaneous Math	325	2016-04-09 17:45
Factoring database issues	Mini-Geek	Factoring	5	2009-07-01 11:51
database.zip	HiddenWarrior	Data	1	2004-03-29 03:53
Database layout	Prime95	PrimeNet	1	2003-01-18 00:49
Is there a performance database?	Joe O	Lounge	35	2002-09-06 20:19

2017-02-16, 14:34	#1554
danaj "Dana Jacobsen" Feb 2011 Bangkok, TH 2²·227 Posts	GMP does a little trial division, a base 210 Fermat test, then n Miller-Rabin tests, using identically-seeded pseudorandom bases. It gives a deterministic test which is good for consistency, testing, and debugging, but also allows one to find pseudoprimes, albeit not as easily as the old "first n prime bases" methods like libtommath still uses. Nicely wrote about this over a decade ago: GNU GMP mpz_probab_prime_p pseudoprimes. I'm not really sure why the base 210 Fermat test is added, as it doesn't really take any less time than a full M-R test as is done right before the M-R tests start. The Euler-Plumb test at least costs ~5% less time and is stronger than the Fermat test, so would make a better pre-test IMO. Far better is, as Paul has said a few times, to switch to BPSW. WraithX offered his code a few years ago on one of the GMP mailing lists but it wasn't taken. I should tidy up my code and do the same since it's faster. It is deterministic and has no known counterexamples (even when the test is weakened to make them easier to find). The time taken is comparable to using an argument of 2-3 for mpz_probab_prime_p.

2018-02-01, 16:49	#1557
MisterBitcoin "Nuri, the dragon :P" Jul 2016 Good old Germany 809 Posts	Does anyone know how to PRP test an cofactor from an Fibonacci Number? Looks like pfgw doens´t like this type of numbers.

2018-02-01, 19:32	#1558
ATH Einyen Dec 2003 Denmark 3⁵×13 Posts	You can always output the entire decimal cofactor to a file and pfgw will read that. How big numbers are you working with?

2018-02-01, 20:47	#1560
ATH Einyen Dec 2003 Denmark 110001010111₂ Posts	21K is nothing I have done at least 750K digits by just writing the entire number to a text file and then running pfgw: pfgw64.exe -f0 -V -l number.txt -f0 for no factoring assuming you did factoring earlier, -V for verbose if you want that, and -l to log results in the "pfgw.out" file or -l<logfilename>. Use -b<base> to run PRP test in another base than 3, like -b2, -b5, -b7 etc. up to -b255.