From arXiv:1301.7007
Pretending to factor large numbers on a quantum computer (Smolin, Smith, Vargo)
N = 354587299551899532016221621119475008825400499497547650506978201009256268364552180775709318276452652316089984125940915011692678699322127626437952340916754401101694942393398796986114303891110264606442388558651298896918167529125072585283561529069045833149085458044971536490488236123032342719854701974702055330361944029796146635105055962858706034637258413294436223612733881541244957256787578366712932408954804647829260155941144405780676687995123372668409240720477985485443153655495464044416749638443397915125535510928642814172984896681146773390333980789565768637726354676678753024806722863674385802601319484610034919950211309093009540594957956178228222703868765170786269198851295753142752503947704413768221119207215221480876964320468397477436679738947595867294693514988034258962044592322773864737596716914996302081975587285523928985393001093345353292339802344738035281643004921149918665815236064716989293685027205309779208792483536435856861813155128983746975168650047620049569410849088691670020716296801864932328763094256328083479904065324168359574206973244925788537649243790221112710763681295487771135243087447315226266209213931674095652048216911945512819495377312187931322592142789485001489833344871961435511910047360734736812014832840402983502352620746227654188482117536899448476546127010571267338768722407534589661423479475134838840104626838051641347817123948816798488784834047858326641760819906992966948006619580318497838879486674968615405796077696761351965322716784614787130464961462851562090254728954342020611465334065624955146855524738182407120328759207306908480563071446913545570922677052690400985646226032392695881701195013830935107656843989911154471193950278950107730349221429151492445765924845971854365441691177223678650239828652770525669972977485371375270616673300194541526561652053155394928754236678105397233257022274282342200952354298403423449776728858821486783470468226452695002996593527614178695275245429581301121106331417186786146442308495638325492501343379943533667191740748211534820379853730691877083942528539000854621063052758727903887688129106643403113169705619311899904858481305060679459430802032118905284796627537032740168043704520077270226719297652780220926165527383461180124631497316203835921031831160181687197774129664680141180854170139904809370511462062235669898350272862689886145264779043245275401271537418445146401952431118324373354960993190118395347174196826048007098715471088712406283428518237722968962878631473783668016914146092518979691440024256035159221892354831540906789710253791305057945251361876320050133719266472957939182533518605946389591064809338994360690234980841989247755331358616272170055093365387596672155433157151339146545373118930562292794711875572014653533038100140905439252036847724360408404774232546401942878800231421626910344281081278216305388078184889109767567478254893671957951737754403325209281049486615968414142618828550508084652551183976898343978994771023762438504588172953877252482623051591922499442701316538880466211509190834246213849980512941160790513257249441273755310745670107815076260546081175916976016600159553696916156907299677384025069458631358698179643840467067437522628304697721524957084545956466958886518881057335562157309517683093771587669273269710690142743804317333579216332286214062939598281480483455670806975129946820368642273953787724284705267144103683177203987376883047129500494898696824232953255873113757347578978257809277321904167217177878976672515522359408378009402407143387778597565494295569927902250050767666924332723725158325468083394216073893463198581373135761145571139995993471008944898117555791511086775950730353669092554198587031850835500747607760851390330479234258280079981276858057262127349159818275895008673060635765352389563946793395313450971874893873569704161228657978315778567085288463502009723922627025686609421284048225610190507570335206787131015524766029049631846926385716073755639969000708073391931617868018694967361522190394952035125269783067194766221272323906814360475290868630208923012179164036085983735643824246615523064849197978217551398231203274241990800815704352105802541280917005306713268282054457196427465173408746589919298859602647517647709753226504353677801754694678666697336302625047413771645854127054752754906960230601433741425478943820896416569084177547682580416515253046632470609640011431981230778557944381857026054508333429833537758185889572134166889296081487694243723204621491394952553741414901724430252885561690937850045828642943492209801913672166578829321051345852769401322166437506715472304530499524263984994190533937022543494927604144729930642315675678036189230393221614960576525703335669945041027365152055579574412670502497628970538358530583415778177055022328930593264650016328201164643257331387742120458095066327831430024747001596359621231252369174409101844438736437858315266946108779141151800556377477506707469599007310299231759300754360323540974886507402140805684292897464783211669582455830578923039655536197400769822261490499867475236050542404832161612695845735514152275026785133897200124109426854987571162068144453489055014586497055134299568235440722244717310938232905732371958904494802809513347111476256115030911273374529603508120033898064894373893351385852991768503183902737153079057664904077587776062549909997744891283441109343053971021216655162711719207028373585558667969241813428794488903796317660882710181290290215856094642563572904860282539784135677839927476637033464998930738742796686640128620923272630180172545665881974962283565208378814689581460871711314663767221236102006204664474455317893551157207881342896856688941673888981550807210018625302957594441170334438348831151000650673799192981407882986789587653580546902745162832189506923934649727346828352271251620599034324381397358884869470399651244166243316866787911322205121407310233451714528628425403496096562315168126981833845796827082647120785562227006525356718270612869805415804935095162605716061024434890607332689100564161111342256215500343733197692859772431311243713297262261757936167225074216356942788711778788009280039137856322497210759
p = 19200079546755208043788502145670962644565082539592344677271116233057677374265185330406795304487914263190662072636603750445244958319471906305054619992493840895454356315018079742573024551364915098196222917505592656399701111158535012527196003143141171107565375921103761192489535991283899768868030610997197057941193788301384925356840915526630432721419360487972156653663749396816731583187062222740819365284873654448464805900788792033088101588445033743097488900639409000279925362619933201439706504546707853810288254711599606525009903719426231146990556873785020501023692130963240749953126360714403411934385429838037318093529490520602775333161645236543673900742063814492055178154240871961342803053595883851060148885682715175492354454895919496808226041535676588909998629212717595725204533557619689628568532503277219758593231003960210428667449775175137355113464291612405770938347336054136193417892395696284969644878587419397025118511173835678856918497340476843981151822753936393438415284562259532725946274954619153439470802826794816873460628749447701517963196331289889880268877975488669856845384063486758917211658934824439411430469198897765504664490525671701566860302600604994891420505724328362982218586950089199844388569358248905219233940228601151530751193629117207861153694353180644277538752068626048814276931514478220406956305360544753533757533602651731156682480712806900803919574751471016869541117827746736553602139151668518124116143362175561314566734029823012868261632323908233576198096916154600888023264627120103908109750544208457938174607367052466388857583094796671645765497531297255387079830529056697297735365569827205457660835709863086032910809416945900478703016844654465993807859855619897695189934445001778347998242457482730579833714866406046997104874770533916896193700019269730005874534486128087333932120639645595377582104692942412694216540960217126237611728784114166152257800535765861537694186942363009111662688683473874040245688817644049151744378243647352370193628308367963132731910962182993571571649918139994774563087499048797489431823180914137084039379815269602298347965704867280274154834865320872563290641229411991826958074462542199615059973523330105642071422411198854298777617828048368908767864646729247705615907317577720222897361292211301379463807503383300814947385213073181332648275822620060993883324461418967817563680237685712137087193696890670471531009895914949733533162552717367854676463006032590457099891058545676094521480005970410137677744043900811512668365463013932510358258797262150424953713774194704111196150327570657167912522754696978763228793016329679121586450437401914882867351034199861481812601249004704113433829496472388970117012344391785521489596399064588536597301413824619888862650156944922652052651343929580625363592770419440450498657743226310655849985633384965750995270262426259463783610590851095864429551274069878588826066040975266553379144063823375859952100319144735104697861168333706619767631167398374649923076346535121565010784152469033959666201721357554336900372204831806324952403
q = 18468012004243200586885450751380649366379781078088279987715065779238563512240821642698240746519848908888538863314146811777562735349842383990567086163202270234479153605098450334971249016496755398003773357052151972923787143841238383036826710002326969663973178227657735325848001954495368601567970009628561986870825780394439849598274041251373721318688499145345993913121828238383790606736771997595630529925354486276625067436089985563008815424294040516093000948612045474327549181231868360756139882688116428895169498745291929770561287646470297265115687387483895368013619997257471764341123285732428939189311363256548896234576403002232606436371401444763435838872754638150464704691037115302635001242854029562463762807770858497146737449843628571647621934352570516005139021147129387725409341092811919553059347635674811730725615295959142079499325819917812886580879387671495319571350857954818154961155967100307910840736419582481531196768438309249368833213399954953500171444271211952594455954004477752823682519163394119191064801737599075725350019163323817981215221348101470698446177886692866845850734698381645621975513332298439876387725945072519444544955988951672961243045362454176002958543468169547377785211809098382638581489343281525541516655146621844431265939594751789647652279726554326674185428437722741359524800315583507714815515303875766821041672499278142585801212148975733472720705737412541961935461361686616350859476011380288544235942812964098355780731059886432669824211205217276923081411398305870459856014134004614097920719675780410011690568388213000815223385679073522081944979933765331520218769929503537517594373554219194566532179113505878044928814690534606638568254357357042753913422485749205954729025087079329038933513243791046103231931467013429494946345040389611215775286692930984369581189082963880754080550863065745759611003460562664434571539900585144073772966191979761575575610876193014563719336468220375800352753194765790998613229326430096620866314392487398763971070581855559310526540801023876149579880675587365810942898804964034364132479348094540491590721769146592341592290325353722923928212844277101301543588882730269074420994947801425179805364110868336391039464347908079529206806056747235446064339813017857678116498351789018935064726714120561012184571042545303364484029311908575889556539612932588916061087100018611541506742289662563529634457054886452529713348307880921587369818548442060025794105215148425586279208114977130525142260634945369806224295120578485674254995575412222341990289944451194943290227557661651585202984294385906785956141309447939044275939636178389404887798648946527438929581534223224707905264709473535937313287694876857699278157956559231814388075818036464096649244543458882362085983915317365113575885609143890422110940069039367341845360415176538206284474541647261198786117315207560909778253371974487292012272567041087110701294986228504764820849761857349563200917181641100369635862758971376996222337337324919989029306933812928255313375808520058118800552746933568638798679596002268651337853
a = 77686554906069116851595396896748508872829767391227439109223314841277681101598247891527093924276297376331925480726454586027525740679667172791721755505822580603781284976866525862036375377203971732741235186942585819046151337257419226632090525241695531971208041122915030807751961501797481370912095756084237524803358135914101301946505352067303719701391298963357303490611728802406088306797014935002827926060724697524788974592236024022258615050033135723043069054476062683139673864572643056040645583367157507463118189262419467218612739212141448472566228406670407624687848622101946824609687469325649701123218591263918762356843441115815922794254662909797904061246169637454343779935531692547643085875195847632839908026660383906748955595904366133542000684895868104840199006615604508689470543581640633988111392111229818039147971571472919306175940357572088670810970737447569774069576094455620915475069916761404720560129532962991197632461565608050410540721478822950371795128621835949856963702166622437137056674472725220969430025322118511972227656991813188700416056665117877435183414475461454492884050823759736353635410852170585508630518839480229319048989879273899633182443157305887861149360197255794463171670979594033319214466490651685720320039510708409536989815541338667873866811683431989070683530829273449623846967244034803825705888454413063124877488397533501762174021757894540809497389965049570340694529853685363563556199246267630123504471103254252018292363045296348077581503592453574075859704912348492295789713424393246571543332960830339272057786293835933456610546742384149125391550133804528633362962890384572999592010518057714406476520887350198864579222363290406297155544460931842508021421211843844173792763164988028133100853915103875597387448285564324871577263536507192121026667516804010636699140175025481989452339630498257434762201164597089156411815838891101897149437669852737901868219219383996398878702889711990589748358056769110816316604605289002757979608130653045690640712653000612283793619074450258251735993639549632201530232832672693030607235018385557125372365322470651275555146154552953072586374150434133978007411677469303225185495474306377083041275967830593851052777357378482614301436370566936056058292203927221644388969239418286238968110267688202288703166800569589709145673128129001286510208080458976973928338666007838609660174496487824104353978426340294302414905233924881598259142672988420057289152775271944037905438583915655458922682125310128010837885819526046222762217537139603728461413369186405170045690500594056084372496205029371475005973359492378758656591928474562733423121998266153593897479465751856486775507185255887953484663756182652027623502598249541740927293003688337254385032721673710541808147643427019061086033878466388317934838584779424691021337226237559600734960304549240361709125978899182900979031855786297551515594299636397234876879796406211203590974956559745043391337778656163030056350719371475665979957380598419063874066857787426262189926220167890359809755172766936843843385254022680790255298415114337585790907673062652756385030374552404077114473245680271217408967949320619767210750009773133558112426254328867278355840757657649236760612662516065063807835049411402937308012421989045834377848271222622260304661756503482059134545468144302111738047206642154563479783777942934328798208340710513082282360163666894777441755608501132236065303573616384981151986910525875269868005864787695732219614282947085239606099789217210063876356625581417040325129360350943722331331576915147806841402642306215842877726181569270068725858628401189053432701072731007242614761800328764495524396351197896142843592663003375557748916737930709732471620687437474665913482817922512150641901227130850761227264795192649287354554570601115373335321993260112660074434638546454394772226581181043770603051467150370868813692963212713276096895386729433449650513222187142161394232745606515270931687434902610371736891381305010709357121801240219345108356141475651149985454957062794930138151162760016089485614479164227488272834457887276332459208866355555320025274423953824839538100709225900716044726465601327434337177980671149536034388615492302914701460003902694923504126725491671341985915689336121105351450399838417839717402886838582106541456655774146096515112992263343670684663934549461323674154688725976109664081661553595940519168967156394456608058049105657335771544839319464700351936213071179217291413400926282989659661854595538931240156499803270756053544310296435988116410553993087734527992205894542720952174425508133189754881919156955811929193191966781308816208523443966889130090212384644262165555381325501001629341823126485843874698136476435360903637213692443724942201699020446048146340466367181122958348711661412468088215513329401649126838868492020943512718719167525882772631465816277179967800081818354547409369942852422598616131972399600335775217947153477997269286425604072099011263458771820941139503227010422225096840885336799345183903647399240608181342871848835612894730505009535329303291420862937862363523356868962066105929282428667833224414171019354322463989134456667156118212177171132474902307850845734903303152583850270928430635189422858159556640242387648505118727279976712594080826305686497570419215682846812242691399382033104079208358737457645310728808353386376210424619283377731957023233940838992549451562327592451660735355255700230213547360960426568078560686158288144399736900984300336175389023060561643737614252481069307752691649934914204556589052737861464774916811361140522019401554336550700124480696590539211844821446831421134112450182866313805439384828406861471681905442918834027976071244164504811135697349218875465213046650119849496224255472066550190013152289632353511813267367273872873914160621340161191444958287592616876010712252931424517232025574953555759702466842612215744635530149437609579838902237107080506262309320260828845720628615740448089334605377377174745031189517091665469004894763918808960181394546612524387322143790260891216857634615417305706473026557928820602015402938203420260179270235206050843670016447924
#number of decimal digits
for v,i in zip('N,p,q,a'.split(','),(N,p,q,a)):
print v,len(str(i))
N 6021 p 3011 q 3011 a 6020
#use leading three decimal digits to calculate number of bits, e.g. N=3.55e6020
from numpy import log2
for m,e in (3.55,6020),(1.92,3010),(1.85,3010),(7.77,6019):
print int(1 + log2(m) + e*log2(10)) #ceil
20000 10000 10000 19998
#check whether really factors
N == p*q
True
#check that a has order 2 in G_N
(a*a) % N
1L
#Euclidean algorithm
def gcd(f,c):
while(c>0): (f,c) = (c,f%c)
return f
#check that (a+1)(a-1) = 0 mod N gives factors
p == gcd(N,a+1), q == gcd(N,a-1)
(True, True)