I’m fixing the polkadot “rust” problem
https://git.hsbp.org/Metaverse_Championship/PMC_Challenges/src/department/grasp/Prequalification_Challenges/rust
I must decode a cryptograhic code. One a part of it’s to search out 2 primes p and q. I do know n = p * q. I’ve some findings, however nonetheless to much less to search out out the reply. Perhaps you could possibly assist me to step additional.
I’ve tried to brute drive the issue. Tried to calculate the prime components of n with python. However leaving the script working the entire evening didn’t clear up the issue. The numbers are too massive.
What I do know
- p and q are primes
- n = p * q
- I do know n. It’s a integer of size 309 (will paste it beneath)
- p and q are created from binary numbers with size 512.
Some discovering:
- Each 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 known 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 =>
Each p and q ought 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 all p or q is decrease size than 155, then the opposite ought to be larger which contradicts to bin_max. Thus each are integer size 155.
This implies the decrease certain for each is the quantity 10^155. The bottom quantity with integer size 155. I known as is lower_bound_155
- One of many primes is < sqrt(n)
If each are larger than that then the multiplication of them might be > n, contradiction.
The integer a part of sqrt(n) I’ve known as “sq” (see beneath). sq has integer size 155.
- decrease certain of primes is n / bin_max
I known as it div_lower_bound (see beneath). div_lower_bound has integer size 155.
Understanding one of many primes we are going to know the opposite. One of many primes is between div_lower_bound and sq. This considerably decreses the ammount of prospects. However nonetheless there are in all probability to a lot prospects (nonetheless > 10^154) to easily calculate with a script. Any further concepts?
n = 149611115935957861847433086030752568567261984621907082786040721407247152663716327519502231379009349403555478392331033952810164148573046688871056752042985601125672198741962270290757469688983708043363147130089304518146209920862956021757294842740478378766019286017585191433945507772906003202456007271670509560001
bin_max = 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084095
sq = 12231562285168556862052042663244771008576122980482704424993591427287253811885458958638241148321682960901030733139435446554924999472329735266020885989949440
div_lower_bound = 11158506798254708627980462589909750889063101381285985042032521742321185338730950171715531148251297904518736872894711197627872202519827978439916380651581752
