Perrin Pseudoprime factoring challenge

[paulunderwood]

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:

104450970899554565481925182690513781089025947342637530828075240970876320691552625909879540391337904807263937263906126185857253947661174544965041234004943902568020420143557521803365045219305925322688260676730496532091650950662335997654910490842252352470759901626395419956442116371761400248633793714203352672363931039677202575561663625542714348264578130315570004959783876689814077767019595169457491798594310769071363352353381529373238891310347111789840124928643731933643576697036147815101475244712600063035967679007969176155987919275988205680363914881425816821412707480088898957417346794821891859842082389855855416382700238576586064520769545808131196513890366503838687776806957944421779031941480067166210929037754138443276710676164196047665850231748197529922446802986573730906034150797463602183178927262429455834540407951007170394891004297835534932251950267838144756839685424719566836562547355317973451239413255034958642675251582321799970531783502320278960829490036243814334135821981350407534632368875726493673711587954743826440929240169237117423510529913733977696070970820591809453869514074874932879342824585179016832679864524166635420679973977211053773372569485406378573548517225883494224927234398084964552067403179498759177420900164340554083045898331160846547245287193375458622252398105589183129268999121540456889460875583823044744944908587244583802038510575420458791203327946776491979630288696494820871011104521109021940436325858841221899072328448064256015303544000459345450194595342404699761880801954870545432877037182987227754331535971523176045851

[paulunderwood]

A Perrin Pseudoprime can be defined as:

ppp(n)=trace(Mod(Mod(x,n),x^3-x-1)^n)==0

And introducing the algorithm "quadratic factor":

qf(n)=l=16;k=2;while(k<l,k++;g=lift(gcd(trace(Mod(Mod(x,n),x^2-k*x+1)^n)-k,n));if(g>1,return([g])))

Here they are in action:

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:

sext(n)=gcd(30,n)==1&&trace(Mod(Mod(x,n),x^6-x^5-1)^n)==1

Sanity check:

for(n=1,100,if(sext(n)!=isprime(n),print([n])))
[2]                                                           
[3]
[5]

[paulunderwood]

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?

[paulunderwood]

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).