mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2019-09-29, 06:22   #12
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

592110 Posts
Default

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)
CRGreathouse is offline   Reply With Quote
Old 2019-09-29, 10:17   #13
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

11×127 Posts
Default

Quote:
Originally Posted by axn View Post
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
R. Gerbicz is offline   Reply With Quote
Old 2019-09-29, 12:35   #14
axn
 
axn's Avatar
 
Jun 2003

111258 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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.
axn is offline   Reply With Quote
Old 2019-09-29, 12:37   #15
axn
 
axn's Avatar
 
Jun 2003

125516 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
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.
axn is offline   Reply With Quote
Old 2019-09-29, 15:05   #16
baih
 
baih's Avatar
 
Jun 2019

2×3×5 Posts
Default

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
baih is offline   Reply With Quote
Old 2019-09-29, 15:48   #17
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

57516 Posts
Default

Quote:
Originally Posted by baih View Post
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
R. Gerbicz is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Factoring composite Mersenne numbers using Pollard Rho jshort Factoring 9 2019-04-09 16:34
Devaraj numbers- necessary and sufficient condition devarajkandadai Number Theory Discussion Group 7 2017-09-23 02:58
Runs of factored numbers henryzz Factoring 8 2017-03-09 19:24
2 holes in bizarre theorem about composite Mersenne Numbers wildrabbitt Math 120 2016-09-29 21:52
Factoring highly composite Mersenne numbers philmoore Factoring 21 2004-11-18 20:00

All times are UTC. The time now is 08:47.

Tue Sep 22 08:47:31 UTC 2020 up 12 days, 5:58, 0 users, load averages: 1.67, 1.78, 1.60

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.