Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
from tqdm import tqdm
import itertools
a = 2821195960321037446898632288244857039957436317435079530335838687362728781410518376744718668720674542350849058769480974085257339164002397119874864207374402
n = 40740327153595270257184780086389953086261120133330698714430641164791044793765728073225136444807495004396268705143115221155717342774153766221474052678956440685995627998728286518422095251317829948639280532042852083900018149268443333895256994879066082385467247811575697036554762935124165948190148187259065768291
c1 = 15299456059343864873123154423984261053470218681269222999806760034801685415379067250969562401321861706151458942840378672266201861683639418278459552822540046204949846903038296947417264184399589146790321851766505139908198090643208050906176021749895564834817658625411004900331537016317911934175301113463305243807
c2 = 3267717973811111609903663596742254164063220133087752184817781695697908008925137677479510304910242404913861174791103168198130734948188615352598500632087933572038101234710649413034772756931619820126488033076322005589499275550327993762859918547931137968414798501640493731151872472338268205516239441527853522482
print(f'a = {a}')
print(f'n = {n}')
print(f'c1 = {c1}')
print(f'c2 = {c2}')
# should be all true when i >= 20
set_bits = []
for i in range(512):
if (a&(1<<i)) == 0: continue
set_bits.append(i)
print(f'set_bits = {set_bits}')
while set_bits[0] < 20: set_bits.pop(0)
md = 1<<set_bits[0]
tg = n % md
parts = []
for p in tqdm(range(1, md, 2)):
q = tg * pow(p, md//2-1, md) % md
parts.append((p, q))
for i in range(1, len(set_bits)):
pos = set_bits[i]
b = 1<<set_bits[i-1]
md = 1<<set_bits[i]
tg = n % md
new_parts = []
print(f'[ ] Trying new pos = {pos}')
for p, q in tqdm(parts):
for dp, dq in itertools.product(range(b, md, 2*b), repeat=2):
p2, q2 = p + dp, q + dq
if p2 * q2 % md != tg: continue
new_parts.append((p2, q2))
parts = new_parts
print(f'[*] pos = {pos} | len(parts) = {len(parts)}')
# Last bit
if True:
b = 1<<set_bits[-1]
cnt = 0
new_parts = []
print(f'[ ] Trying new pos = {pos}')
for p, q in tqdm(parts):
for dp, dq in itertools.product(range(b, 2**512, 2*b), repeat=2):
p2, q2 = p + dp, q + dq
if p2 * q2 != n: continue
cnt += 1
new_parts.append((p2, q2))
assert cnt < 10000000, 'Too heavy!'
parts = new_parts
print(f'[*] pos = {pos} | len(parts) = {len(parts)}')
print(f'[*] parts = {parts}')
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment