Ask Your Question
1

Cant convert x to integer

asked 2013-04-14 22:25:07 -0500

H_DANILO gravatar image

Im trying to create a function to decrypt based on Rabin, and thats what a did so far:

def decriptograph(n,m):

p,q = factor(n)
p = p[0]
q = q[0]
mp = m % p
mq = m % q
if (((p-3) % 4) <> 0) or (((q-3) % 4) <> 0):
    return -1

x1 = mp**((p-1)/4) % p  
return x1

Happens that if i try to use decriptograph(328419349,249500293)

It wont work, gives the following exception:

Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "_sage_input_25.py", line 10, in <module> exec compile(u'open("___code___.py","w").write("# -- coding: utf-8 --\n" + _support_.preparse_worksheet_cell(base64.b64decode("ZGVjcmlwdG9ncmFmYXIoMzI4NDE5MzQ5LDI0OTUwMDI5Myk="),globals())+"\n"); execfile(os.path.abspath("___code___.py")) File "", line 1, in <module> File "/tmp/tmp8wJFUs/___code___.py", line 3, in <module> exec compile(u'decriptografar(_sage_const_328419349 ,_sage_const_249500293 ) File "", line 1, in <module> File "/tmp/tmpR_b1R1/___code___.py", line 12, in decriptografar x1 = mp*((p-_sage_const_1 )/_sage_const_4 )%p File "integer.pyx", line 2857, in sage.rings.integer.Integer.__mod__ (sage/rings/integer.c:18585) File "integer.pyx", line 6066, in sage.rings.integer.integer (sage/rings/integer.c:35628) File "integer.pyx", line 714, in sage.rings.integer.Integer.__init__ (sage/rings/integer.c:7299) File "expression.pyx", line 741, in sage.symbolic.expression.Expression._integer_ (sage/symbolic/expression.cpp:5167) TypeError: unable to convert x (=114611606108095614727240369588925471316913128619468960102905019822257329106821771893398898773005180268594772459861048172798085840783082345998445110510925629665644249037359476360933399737179630079098113958399608146265304477904662677015387609715956179962609881428193769707630781727480686062280101195750122191858490225083529433496064502358119123164716230123613730841849446963451259514723153261145565905196308377570101576542388938400762965225303237213512726029071310054058245945823740447421047288808213060793395184467847927279830814326604613783496390943538300094005253658400924784792904353822405266588885492012938885240054608722428301317223366293083940384789334238950403458146185770921014882376350582365257635670460852184194863071570810015488668951014937035671004400310457828110545549315566950520262511400497177401558009497278348110949857734953474707330229573760525859894912657753135699789359519485834733133119691282289620959856982866367998245040732087436435792805916247853058415013276638473024216303188143049559941099812990599056979630728507850090320453658901654567858537597955052831763044092908879704819309183325707993850428406735655700750998109243474069231436200079019472214957980570330929220006938887605436340206597074899150859204919151663535529556999544153287645689405946209978076869942957904786162779295004867564728537388532106822876212792057291374256828601435388932917096907239500602091220270447304572497290945261753837148976309078563480107642965064679949213102529242293649060632214945425657085248939947331491010614662096233282100676337926743050738208594304251869891540177977973149675879106621955778232366497114832251893433437292516085287847010403278136821441267498433380928516420965366678503138156955215873130292281838603523117891986304359327412814916520328094981460590656298651735412662055011499979286568438048527045034787562451112660325251810933265224448533697256485318736143662940214768372196714610978392149497663323804090946081161177175699956428030671628909407965415189596035891785472936028611637812251358406477234868843692296383907110765073141666671377384300630693009219183675459367306183720715684038010984917820424604612569365535048335150656720341180635808399823789359104(12056343698073619262211017905181752133267539008241148956053617489898400451426401067082093344887211656962991084710892590406496655178308713648931458643321637418027743230928508655984670908684496995061690129297848014102259242870573979695261676493099753453198057674873054960533867270864720683281393523575269104428221555021368341060309220263446093009283257004121443655032438588495127705709652461430809237915452772363803720669806187220703217404512432990218769866497698695100658304562919648043857963090166306869747496186559131989553227769587674886558354863786894899153740176969773049050812889869507484039933932653834554342005842050200629424191058721049360407211914801360923240985045974341861698500692293561614936007148209454757005379209258925040525687079831671855412203664956091215402099304534994607510587927164301506374749824767320375241605227872753821866259661896226686692999514602399085749922929788823177002698406680905984199300036994500103730308895769545246518246048594247166343709311327856536838196210215853385013358074581143893649271580171186327414791410819825254706630787864799183119291583804075745850276247404650903111686279516242437556975903983741593369538929697116127617104543894461313704597132845783332830055085350536430507443232574426908617356018887638179530853697790453747599264025685018463456736386746618492026816970584179085430693193047354365138192002417832457316709111876051961381088763372941731134471875052644353627907090090227547682832820594570559633695580057181947768510683996652909982140581855048134996003225628476331290529233101204278526353994703264723894431796784926467041421385756262313400007719117482316102210519903588580087413497118872775197923499941254416744086248330646191595092806996080207909186396006876011034665935277663110103179616049602442266811745094129503256429528369303528979070492607758001318356252987118006049159289209072452514378709583907243333493087694719653818772605567516808389797599507332870973604664146543980423387269739365869214372033172017652552710191094366551617447244209252370209015148133893471665739384776105160517037571315597858647336055153246464309480245871363466942265245008876041278442464208789301312081594462633169888237574753875617858316453565882505858966614458040206577967224429024454863715260843539223511376608843966037003325427522012419589624386791528084394645330148741798653369733987247813912342422098803414547811627745621730064927970333640915478415962795326183924716953970215796037179761421442791168077613602460714841166282383055272890260702863434579017235301087850364742218701940436817306642290722631947332591622967387592390840507311877474882327437994274940127129248428759583625837920781559436812783587756642091136594185630463521578562811930806244924087446517210042390074516355820297228274544583285282625214750258196137068047027915366182372170978245339433571334288306634765482896504182461345564973141361963652675659575206261057011291228078389568573458593941630327673014807336460509773824*sqrt(42))) to an integer

Yeah, i know, pretty big number but it works really really smooth on my python(without sage)

Any help?

edit retag flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted
2

answered 2013-04-15 00:01:57 -0500

You probably want (p-3)/4 instead of (p-1)/4 in the definition of x1, since this affectation takes place only if the if clause failed, meaning that (p - 3) % 4 is zero.

The reason it works in Python is that in Python, if k is an integer, k / 4 returns the integer part of k over 4, while in Sage, it returns a rational. The error message said:

TypeError: unable to convert x (=1146...9104*(1205...3824*sqrt(42))) to an integer

which tells you a square root was being extracted, and this could only happen at the exponentiation step mp**((p-1)/4) (in your example, (p-1)/4 is a half-integer).

Note that you can force integer division by using // instead of /, so you could write x1 = mp**((p-1)//4) % p.

Combining these two tricks, your code becomes:

sage: def decriptograph(n,m):
....:         p, q = factor(n)
....:         p, q = p[0], q[0]
....:         mp, mq = m % p, m % q
....:         if (p - 3) % 4 or (q - 3) % 4:
....:                 return -1
....:         x1 = mp ** ((p - 3) // 4) % p
....:         return x1
....: 
sage: decriptograph(328419349,249500293)
5641
edit flag offensive delete link more

Comments

you're so right dude, except fort the part of (p-3)%4 which was in fact (p+1)/4, but you told that i realized that i was going wrong there! I just mistyped +1 for -1 there, thank you again!

H_DANILO gravatar imageH_DANILO ( 2013-04-15 01:21:34 -0500 )edit

@H_DANILO - if you like the answer enough, you can "accept" it :)

kcrisman gravatar imagekcrisman ( 2013-04-15 02:46:00 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2013-04-14 22:25:07 -0500

Seen: 1,354 times

Last updated: Apr 15 '13