mersenneforum.org Condition on composite numbers easily factored
 Register FAQ Search Today's Posts Mark Forums Read

 2019-09-29, 06:22 #12 CRGreathouse     Aug 2006 16E716 Posts This is the test code I used while composing the above posts to generate numbers of the OP's form; I wonder if it's similar to your code, axn? Code: baih(N,P=N\3)= { my(p,lower,upper,k,q); if(P>=N/2,error("Need p small")); while(p%3<2, p=randomprime([2^(P-1),2^P-1]) ); lower=ceil((2^(N-1)/p-3)/(p-1)); upper=(2^N\p-3)\(p-1); while(q<1, k=random(upper-lower)+lower; q=k*(p-1)+3; if(p*q%4==1||!ispseudoprime(q),q=0) ); \\print(p); p*q; } baih(3068)
2019-09-29, 10:17   #13
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

137810 Posts

Quote:
 Originally Posted by axn Try this. q = O(p^2)
Good challenge. Solved:
Code:
n=3288315334013507348031117171885468096161021677564004034300356172248483753561621058705350647739894009\
5346045680550009445472595322983664958188142787148092914918061445039917611408596599725591252362294564\
1600699758076211854269675560352903000577560129603812320249402228524238334224780394198927618762027764\
4694175629521539892657010544312115079861771453079179141384844469970549673293813989678369426258452910\
3551493881299669360832439809441334130754552040177986894056672293223072559252965382679545203159671871\
1052801385883659044607163858197456954994787562252648007765822584016182739358104036624722033623683457\
3334375676353282746086370455038295247170962866302648507514375876708778979433419266589795636925613207\
4747459949682410108234198907723945838288102283178012219388623968160789028801889034265955398723460901\
5349542235839252138730727703428196783513008435899978778140980069771163397970731725281106467346639407\
481050648890548443151347;

p=484605015374629056777963894537847106303895551675266313154360900707104424961427719036266452196533774\
52921936399517882322789881804586540944802829882322554400675112952961990074662282674675063947229415372\
10158614848604710460460300049181316857625972449622618772532492044500653582851152895649758081518411705\
6344899;
q=678555778353106856699471351544625270538870277275101480850221325370922821493334863046535648959050812\
25688605158423860427793393677368543359664716921597907268575312832766558132199830099232360905729404728\
99121337787838935076965193459155301627652246520120302228518250201648597012572946836549688528687425909\
44431888146970279878990658770601477218446643121167732647451536410730645312792077195198632467755596788\
25155503616310435258635806796447200837691193982379038095497921562247764105338407437089023151285738935\
17162015165055647773150505612736034197993659591091727613875121131926185630357234439967667412188642741\
148076798353;

n==p*q
%42 = 1

2019-09-29, 12:35   #14
axn

Jun 2003

123C16 Posts

Quote:
 Originally Posted by CRGreathouse This is the test code I used while composing the above posts to generate numbers of the OP's form; I wonder if it's similar to your code, axn?
Similar-ish, but less sophisticated. I hardcoded the sizes, and didn't bother with getting exact bit-lengths (so randomprime(2^1024) and random(2^2048)). Also for q, I started at random point and walked along an AP until an appropriate prime is found.

The only additional thing is the use of setrand.

2019-09-29, 12:37   #15
axn

Jun 2003

22·3·389 Posts

Quote:
 Originally Posted by R. Gerbicz Good challenge. Solved:

If you don't mind, what is the procedure?

I wonder if there is a family of similar conditions with which you can generate backdoored keys.

 2019-09-29, 15:05 #16 baih   Jun 2019 32 Posts my solution are :qp =c lets n is integer e= (c+1)/4 s= n^e Mod c q= gcd(s-n,c) for your example : Code: gcd(328831533401350734803111717188546809616102167756400403430035617224848375356162105870535064773989400953460456805500094454725953229836649581881427871480929149180614450399176114085965997255912523622945641600699758076211854269675560352903000577560129603812320249402228524238334224780394198927618762027764469417562952153989265701054431211507986177145307917914138484446997054967329381398967836942625845291035514938812996693608324398094413341307545520401779868940566722932230725592529653826795452031596718711052801385883659044607163858197456954994787562252648007765822584016182739358104036624722033623683457333437567635328274608637045503829524717096286630264850751437587670877897943341926658979563692561320747474599496824101082341989077239458382881022831780122193886239681607890288018890342659553987234609015349542235839252138730727703428196783513008435899978778140980069771163397970731725281106467346639407481050648890548443151347,33044430344567968457504390023730807700313470204127206103541738009757190061479952532666748417160803343549369591197775495859904337324192484080277708616305115571121880098481299055289260814667885642311554608842472462733334431317525082158702950796446483597745583328368895423573229578085998903425664004102550943684031377722419489648041589886974882817389337884568062324779444848203311395820530527814776447027532071511471572577892574608732728121724263102797210907168796982692953052763795367557134923837558068441166143485009803333253526113177756420178435576304830147949361380748235159254432926482497724084258840911722885237709628903306000933805702588271038163052264047981072345113780656741415339127876436623493274377738582532331423336092170940538472743424073894604109693078215734638692617988656076012724887785585490772500772435031723175876509289016224044113157928408771933675849061252766798346330233372053354515046214836702864157330) 48460501537462905677796389453784710630389555167526631315436090070710442496142771903626645219653377452921936399517882322789881804586540944802829882322554400675112952961990074662282674675063947229415372101586148486047104604603000491813168576259724496226187725324920445006535828511528956497580815184117056344899L Last fiddled with by LaurV on 2019-10-01 at 10:28 Reason: Replaced quote tag with code tag, it made a mess of the page
2019-09-29, 15:48   #17
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

56216 Posts

Quote:
 Originally Posted by baih my solution are :qp =c lets n is integer e= (c+1)/4 s= n^e Mod c q= gcd(s-n,c) for your example :
Yes, more detail:
If n=p*q, and (n+1)/4==1 mod (p-1) then
(p-1) | e=(n-3)/4 with Fermat (for every b)
b^e-1 is divisible by p so p|gcd(b^e-1,n) and in general it is in fact p (and not n).

So (partial) factorization is easy when we know p|n and n mod (p-1).
Say we know that n==r/s mod (p-1) for tiny r,s (in solution just try all r,s pair).

Last fiddled with by R. Gerbicz on 2019-09-29 at 15:48

 Similar Threads Thread Thread Starter Forum Replies Last Post jshort Factoring 9 2019-04-09 16:34 devarajkandadai Number Theory Discussion Group 7 2017-09-23 02:58 henryzz Factoring 8 2017-03-09 19:24 wildrabbitt Math 120 2016-09-29 21:52 philmoore Factoring 21 2004-11-18 20:00

All times are UTC. The time now is 12:05.

Sun Aug 9 12:05:39 UTC 2020 up 23 days, 7:52, 2 users, load averages: 1.56, 1.65, 1.73