Hello! So I decided to start trying to implement MTProto protocol (Telegram) in
Nim, did the most basic things so I can get a reply from the server for the
first time.
To continue I need to decompose a number `pq` into two prime cofactors `p` and
`q`, such as `p` < `q`. So basically I need to find the largest prime cofactor
of a number and then divide the number by that cofactor to get the second one.
The Python version I found runs really fast in under 100ms:
from random import randint
from math import gcd
def brent(N):
if N % 2 == 0:
return 2
# y, c, m = randint(1, N - 1), randint(1, N - 1), randint(1, N - 1)
y = 398563423414958448
c = 259203014236224986
m = 359097073186387306
g, r, q = 1, 1, 1
while g == 1:
x = y
for i in range(r):
y = ((y * y) % N + c) % N
k = 0
while k < r and g == 1:
ys = y
for i in range(min(m, r - k)):
y = ((y * y) % N + c) % N
q = q * (abs(x - y)) % N
g = gcd(q, N)
k = k + m
r *= 2
if g == N:
while True:
ys = ((ys * ys) % N + c) % N
g = gcd(abs(x - ys), N)
if g > 1:
break
return g
def factors(n):
a = brent(n)
b = n // a
return (a, b) if a < b else (b, a)
print(factors(1243804461473944423))
Run
I tried my hand at porting it to Nim but I guess I failed:
import random, math
randomize()
proc brent*(n: uint64): uint64 =
if n mod 2 == 0:
return 2
var
# y = rand(1'u64 ..< n - 1)
y = 398563423414958448'u64
c = 259203014236224986'u64
m = 359097073186387306'u64
g, r, q = 1'u64
x, k, ys = 0'u64
while g == 1:
x = y
for i in 0 ..< r:
y = ((y * y) mod n + c) mod n
k = 0'u64
while k < r and g == 1:
ys = y
for i in 0 ..< min(m, r - k):
y = ((y * y) mod n + c) mod n
q = q * uint64(abs(int64(x - y))) mod n
g = gcd(q, n)
k = k + m
r *= 2
if g == n:
while true:
ys = ((ys * ys) mod n + c) mod n
g = gcd(uint64(abs(int64(x - ys))), n)
if g > 1:
break
result = g
proc factors(n: uint64): (uint64, uint64) =
let a = brent(n)
let b = n div a
if a < b: (a, b) else: (b, a)
echo factors(1243804461473944423'u64)
Run
As far as I can see one of the issues if that there's an overflow when two big
uint64's are multiplied. So can someone recommend a good way to port this
algorithm, or maybe I can use some other algorithm which won't use such big
numbers for multiplication? (I also tried porting
[https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm](https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm)
and succeeded, but it's quite slow)
