mersenneforum.org Perrin Pseudoprime factoring challenge
 Register FAQ Search Today's Posts Mark Forums Read

 2022-10-11, 12:34 #1 paulunderwood     Sep 2002 Database er0rr 2·33·83 Posts Perrin Pseudoprime factoring challenge I claim to be able to factor any Perrin Pseudoprime (PPP) that you give me. The one given on Page 19 of https://arxiv.org/pdf/2002.03756.pdf which has a 1551 digit factor of: Code: 104450970899554565481925182690513781089025947342637530828075240970876320691552625909879540391337904807263937263906126185857253947661174544965041234004943902568020420143557521803365045219305925322688260676730496532091650950662335997654910490842252352470759901626395419956442116371761400248633793714203352672363931039677202575561663625542714348264578130315570004959783876689814077767019595169457491798594310769071363352353381529373238891310347111789840124928643731933643576697036147815101475244712600063035967679007969176155987919275988205680363914881425816821412707480088898957417346794821891859842082389855855416382700238576586064520769545808131196513890366503838687776806957944421779031941480067166210929037754138443276710676164196047665850231748197529922446802986573730906034150797463602183178927262429455834540407951007170394891004297835534932251950267838144756839685424719566836562547355317973451239413255034958642675251582321799970531783502320278960829490036243814334135821981350407534632368875726493673711587954743826440929240169237117423510529913733977696070970820591809453869514074874932879342824585179016832679864524166635420679973977211053773372569485406378573548517225883494224927234398084964552067403179498759177420900164340554083045898331160846547245287193375458622252398105589183129268999121540456889460875583823044744944908587244583802038510575420458791203327946776491979630288696494820871011104521109021940436325858841221899072328448064256015303544000459345450194595342404699761880801954870545432877037182987227754331535971523176045851
 2022-10-11, 21:41 #2 paulunderwood     Sep 2002 Database er0rr 2·33·83 Posts A Perrin Pseudoprime can be defined as: Code: ppp(n)=trace(Mod(Mod(x,n),x^3-x-1)^n)==0 And introducing the algorithm "quadratic factor": Code: qf(n)=l=16;k=2;while(k1,return([g]))) Here they are in action: Code: for(n=4,100000000,if(!isprime(n)&&ppp(n),print([n,qf(n)]))) [271441, [521]] [904631, [7]] [16532714, [22]] [24658561, [5149]] [27422714, [22]] [27664033, [3037]] [46672291, [4831]] Of course, I have checked out every PPP I can lay my hands on, including Carmichael Numbers (2^64), and they all factor with qf(n). The next challenge is to find a pseudoprime to: Code: sext(n)=gcd(30,n)==1&&trace(Mod(Mod(x,n),x^6-x^5-1)^n)==1 Sanity check: Code: for(n=1,100,if(sext(n)!=isprime(n),print([n]))) [2] [3] [5] Last fiddled with by paulunderwood on 2022-10-11 at 21:57
 2022-10-12, 05:00 #3 paulunderwood     Sep 2002 Database er0rr 2×33×83 Posts I have a question: The cubic x^3-x-1-n==0 can be solved with radicals. Given such a solution, is it possible to input it into qf(n) and get a factorisation of n? Last fiddled with by paulunderwood on 2022-10-12 at 05:01
 2022-10-13, 20:02 #4 paulunderwood     Sep 2002 Database er0rr 2·33·83 Posts The PPP 1260330659197 is difficult to factor with the above qf(n). Thanks to David Broadhurst for finding this number. Apart from using x^2-k*x+1 -- which has the advantage of being quick -- I could use any other polynomial. And there is nothing really special about the PPP polynomial x^3-x-1. Consequently, qf(n) can be applied to any composite, but sometimes there will be no factorisation. Having said this, I have easily factored millions of PPP (except the one above). Last fiddled with by paulunderwood on 2022-10-13 at 20:35

 Similar Threads Thread Thread Starter Forum Replies Last Post siegert81 Factoring 12 2016-05-28 18:36 Random Poster Factoring 74 2012-09-18 22:56 koders333 Factoring 5 2006-03-28 13:50 Xyzzy Factoring 65 2005-09-05 08:16 philmoore Factoring 63 2005-01-06 03:09

All times are UTC. The time now is 17:52.

Sat Jan 28 17:52:31 UTC 2023 up 163 days, 15:21, 0 users, load averages: 0.76, 0.81, 0.88