mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2022-10-11, 12:34   #1
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·33·83 Posts
Talking 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
paulunderwood is offline   Reply With Quote
Old 2022-10-11, 21:41   #2
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·33·83 Posts
Default

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(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:

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
paulunderwood is offline   Reply With Quote
Old 2022-10-12, 05:00   #3
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×33×83 Posts
Default

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
paulunderwood is offline   Reply With Quote
Old 2022-10-13, 20:02   #4
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·33·83 Posts
Default

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
paulunderwood is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Simple factoring challenge + questions siegert81 Factoring 12 2016-05-28 18:36
Factoring Challenge in TAOCP Random Poster Factoring 74 2012-09-18 22:56
Regards RSA factoring challenge koders333 Factoring 5 2006-03-28 13:50
Perpetual ECM factoring challenge thread... Xyzzy Factoring 65 2005-09-05 08:16
Odd Perfect numbers - a factoring challenge 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔