[ad_1]
I’m fixing the polkadot “rust” problem
I have to decode a cryptograhic code. One a part of it’s to seek out 2 primes p and q. I do know n = p * q. I’ve some findings, however nonetheless to much less to seek out out the reply. Maybe you possibly can assist me to step additional.
I’ve tried to brute power the issue. Tried to calculate the prime components of n with python. But leaving the script working the entire night time didn’t remedy the issue. The numbers are too huge.
What I do know
- p and q are primes
- n = p * q
- I do know n. It is a integer of size 309 (will paste it beneath)
- p and q are created from binary numbers with size 512.
Some discovering:
- Both primes have integer size 155:
Becase each primes are created from a binary of size 512 we all know the theoretical max of them. it s a binary with 512 consecutive ones which I referred to as bin_max and I’ve calculated it (see beneath). bin_max has integer size 155. bin_min is 0 (512 consecutive zeros, however that is irrelevant, due to the next discovered boundaries).
n = p*q and n integer size is 309 =>
Both p and q needs to be of integer size 155, as a result of solely multiplying two size 155 quantity will give us a size 309 quantity. if one in every of p or q is decrease size than 155, then the opposite needs to be increased which contradicts to bin_max. Thus each are integer size 155.
This means the decrease certain for each is the quantity 10^155. The lowest quantity with integer size 155. I referred to as is lower_bound_155
- One of the primes is < sqrt(n)
If each are increased than that then the multiplication of them will probably be > n, contradiction.
The integer a part of sqrt(n) I’ve referred to as “sq” (see beneath). sq has integer size 155.
- decrease certain of primes is n / bin_max
I referred to as it div_lower_bound (see beneath). div_lower_bound has integer size 155.
Knowing one of many primes we’ll know the opposite. One of the primes is between div_lower_bound and sq. This considerably decreses the ammount of potentialities. But nonetheless there are in all probability to a lot potentialities (nonetheless > 10^154) to easily calculate with a script. Any extra concepts?
n = 149611115935957861847433086030752568567261984621907082786040721407247152663716327519502231379009349403555478392331033952810164148573046688871056752042985601125672198741962270290757469688983708043363147130089304518146209920862956021757294842740478378766019286017585191433945507772906003202456007271670509560001
bin_max = 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084095
sq = 12231562285168556862052042663244771008576122980482704424993591427287253811885458958638241148321682960901030733139435446554924999472329735266020885989949440
div_lower_bound = 11158506798254708627980462589909750889063101381285985042032521742321185338730950171715531148251297904518736872894711197627872202519827978439916380651581752
[ad_2]