FactorDB PRP's - Page 21

RichD · 2014-06-24, 22:13

I'll jump in at 2600 and do a few dozen here or there when I have time.

schickel · 2015-07-14, 10:10

I decided to take a break from factoring for a day or two and found somebody doing this. Is there a good reason to search for these particular forms? (It started with a bunch of 10^775+x and 10^775+x/y, now it looks like they're moving to 10^500+x....) I was going to try and clear all the PRPs below 3000 digits, but that victory apparently won't last long.

The bulge at 1000 digits is the same thing with lots of 1-8 digit divisors.....

schickel · 2015-07-25, 22:13

While clearing the <3000 digit PRPs I came across this one at 2531 digits that is apparently not a PRP:

Code:

Version=3.0.9
WebSite=http://www.ellipsa.eu/
Task=Certification
ID=B3A3C031BF491
Created=07/25/2015 02:29:23 PM

[Common]
Path=C:\aliquot\Primo\work\
Selected=1
Processed=1
Certified=0
Candidate #1=Aborted, 0.00s

[Candidate #1]
Input=primo_1100000000781996714.in
Status=Candidate not strong pseudoprime to the base 2

The latest Primo 4.1.1 also reports this problem.

wombatman · 2015-07-26, 03:44

Did you get Primo working on Windows?

schickel · 2015-07-26, 04:45

Quote:

Originally Posted by wombatman

Did you get Primo working on Windows?

No, I run the latest version in VirtualBox on my six core AMD. It seems to suffer from very little penalty running in a VM.

paulunderwood · 2015-07-26, 04:46

Quote:

Originally Posted by schickel

While clearing the <3000 digit PRPs I came across this one at 2531 digits that is apparently not a PRP:

Code:

Version=3.0.9
WebSite=http://www.ellipsa.eu/
Task=Certification
ID=B3A3C031BF491
Created=07/25/2015 02:29:23 PM

[Common]
Path=C:\aliquot\Primo\work\
Selected=1
Processed=1
Certified=0
Candidate #1=Aborted, 0.00s

[Candidate #1]
Input=primo_1100000000781996714.in
Status=Candidate not strong pseudoprime to the base 2

The latest Primo 4.1.1 also reports this problem.

I can confirm it is not PRP with base 2, using my Ruby program and with Pari/GP

wombatman · 2015-07-26, 04:55

Quote:

Originally Posted by schickel

No, I run the latest version in VirtualBox on my six core AMD. It seems to suffer from very little penaly running in a VM.

Ah! Perfect. That's good to know. Thank you.

danaj · 2015-07-26, 06:53

Quote:

Originally Posted by schickel

While clearing the <3000 digit PRPs I came across this one at 2531 digits that is apparently not a PRP [...] The latest Primo 4.1.1 also reports this problem.

Not a base-b pseudoprime for any b in 2-1000. I suspect whatever is doing the PRP testing is interpreting ## differently, as described on the Other Factordb Problems page. Factordb inteprets n# as primorial (product of all primes below n) and n## as pn_primorial (product of the first n primes = p_n #). PFGW interprets it differently (as far as I can tell, adding more # symbols beyond the first means nothing -- to get pn_primorial one uses p(n)#), Probably a mismatch there, especially since if we give the expression to PFGW it will interpret it as (776*776#+1)/92857 which happens to be a proven prime, explaining why it keeps answering that it is PRP.

schickel · 2015-07-26, 07:47

Quote:

Originally Posted by danaj

Not a base-b pseudoprime for any b in 2-1000. I suspect whatever is doing the PRP testing is interpreting ## differently, as described on the Other Factordb Problems page. Factordb inteprets n# as primorial (product of all primes below n) and n## as pn_primorial (product of the first n primes = p_n #). PFGW interprets it differently (as far as I can tell, adding more # symbols beyond the first means nothing -- to get pn_primorial one uses p(n)#), Probably a mismatch there, especially since if we give the expression to PFGW it will interpret it as (776*776#+1)/92857 which happens to be a proven prime, explaining why it keeps answering that it is PRP.

Darn it, then. I wanted to clear out everything less than 3000 digits, but it looks like there's going to one lone holdout.

What are the chances that a factor could be found and mark this particular number composite?

schickel · 2015-07-27, 12:39

Quote:

Originally Posted by schickel

Darn it, then. I wanted to clear out everything less than 3000 digits, but it looks like there's going to one lone holdout.

What are the chances that a factor could be found and mark this particular number composite?

Well, well, well; speak of the devil:

Code:

Using B1=3000000, B2=4016636513, polynomial Dickson(6), sigma=812894513
Step 1 took 7453019ms
Step 2 took 937321ms
********** Factor found in step 2: 3520514800699633460823911989
Found probable prime factor of 28 digits: 3520514800699633460823911989
Composite cofactor 24161566278972550168408072730476970270476506749746082631557024528395695782803180302528901974928792885843370994742546253269566191389510670086924201474323882638243272173133991807101066434945347589538453777932339535482149759390471307807968861772331584750143338558511366322783128808270090099618922033959948365965629440705821579473922412910166602416335093363891961621126854467819583799664849144832117400117073353378200458944117620403510205128014387588665382985138713846871522931764536280956167028061636398258999495413574237206865765450810276151064676931192134907232483157481157399849344344582879933388316958978343865266809301614535675920027605216864618745186933336761647508502311235301585740503865029892543865819795996999407103301445253186643736704427289340813496113280780306147234760035172202082510475653167315028615806150490505538734359120212827809073207378884803010753947876397592109025128579782912615015916326494283948595396723278341576806783816638865671808809059992810380613449439059055859082806707098680516929491648459108165839627544142122381913130807019058016559735444773711331151212109972526013084986580194545721321205046034160237388062940244840886695459253044179885922311194591936130792509180070888550608961996353688750803470928312640926055381429757257092145039908251169784522739155321874921647643952899105386398973109508642324423968667082678908498688824064056127707624704173116945707364186087146816630508704039613197077417327647311305789295169796969410427693084849675496242888052810460495111396509364639918807958503766386601806357500768745804894627418957949730056497988175730693991374100821738942826145199946546843414472497928700233431919366424515219106447954692536321065176993725415368743771365746873209620597533896768121799899924748720886385620392061119914467821536322499655907453218983871830172444007957875127142412773964243730748986971452929937201275845708811715639505216097748970282331896090384679630642845255077900316829736554123264865108550135976458966451810796154771122939889096533135610807051003754109921064624260361019832246872168646172491233363953874520707710003582405755793957808153409420439598023294713567809953743591989935898064596902973996382880492227661789713162658746420683201707105843604621272107043734947668423774968416500681536033798057633373953966620607158525462543925766704083421012418800231819176046496240456926478224477708601040508925387371836687606367382424344627871317474599433393599081928397742231769155425735912076830612946936948642557382532592054798309878465183739056917 has 2504 digits
Using B1=3000000, B2=4016636513, polynomial Dickson(6), sigma=4288230846
Step 1 took 7366145ms
Step 2 took 942454ms
Using B1=3000000, B2=4016636513, polynomial Dickson(6), sigma=1744904676

Unfortunately, it doesn't work. It accepted the two factors, but it didn't mark them as belonging to the "PRP".

chris2be8 · 2015-07-27, 16:13

My first thought was to click the (show) link to get the decimal expansion of it and check that ECM and Primo are working on the same number as factordb.

Then I tried experimenting with that approach. bc says that the decimal expansion mod 3520514800699633460823911989 is zero. And when I put (776*776##+1)/92857/3520514800699633460823911989 into factordb it shows a composite matching the cofactor schickel found. So I think factordb is confused, it knows of the factor of the PRP but still thinks it's PRP.

I think this needs SYD to act.

Chris

2015-07-14, 10:10	#222
schickel "Frank <^>" Dec 2004 CDP Janesville 2122₁₀ Posts	I decided to take a break from factoring for a day or two and found somebody doing this. Is there a good reason to search for these particular forms? (It started with a bunch of 10^775+x and 10^775+x/y, now it looks like they're moving to 10^500+x....) I was going to try and clear all the PRPs below 3000 digits, but that victory apparently won't last long. The bulge at 1000 digits is the same thing with lots of 1-8 digit divisors..... Attached Thumbnails

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
A suggestion for factordb.	enzocreti	FactorDB	15	2021-06-24 07:15
Other Factordb Problems	wblipp	FactorDB	470	2021-06-13 16:58
Accessing FactorDB from Python	shortcipher	FactorDB	21	2018-12-03 17:03
Extending Factordb	carpetpool	FactorDB	6	2017-01-23 11:04
FactorDB question	Raman	Factoring	15	2010-01-28 10:24

2014-06-24, 22:13	#221
RichD Sep 2008 Kansas 3376₁₀ Posts	I'll jump in at 2600 and do a few dozen here or there when I have time.

2015-07-26, 03:44	#224
wombatman I moo ablest echo power! May 2013 1769₁₀ Posts	Did you get Primo working on Windows?

2015-07-27, 16:13	#231
chris2be8 Sep 2009 2·1,039 Posts	My first thought was to click the (show) link to get the decimal expansion of it and check that ECM and Primo are working on the same number as factordb. Then I tried experimenting with that approach. bc says that the decimal expansion mod 3520514800699633460823911989 is zero. And when I put (776*776##+1)/92857/3520514800699633460823911989 into factordb it shows a composite matching the cofactor schickel found. So I think factordb is confused, it knows of the factor of the PRP but still thinks it's PRP. I think this needs SYD to act. Chris