Mark Dickinson <dicki...@gmail.com> added the comment:
Thanks, Tim; very interesting. I hadn't seen this factoring algorithm before.
> That wants the _ceiling_ of the square root.
Looks like what it actually wants is the ceiling analog of isqrtrem: that is,
it needs both the ceiling of the square root *and* the difference between the
square of that ceiling and the original number.
The description of the algorithm in section 2 is a bit odd: they define m :=
s*s % n, using an expensive modulo operation, when all they need is a
subtraction: m := s*s - n*i. This is noted in section 3 ("to reduce modulo Mn
at step 3, one may simply subtract Mni from s2"), but they fail to note that
the two things aren't equivalent for large enough i, possibly because that
large an i won't be used in practice. And in the case that the two quantities
differ, it's the subtraction that's needed to make the algorithm work, not the
mod result.
Here's a Python version of Hart's algorithm:
from itertools import count
from math import gcd, isqrt
def isqrtrem(n):
""" For n >= 0, return s, r satisfying s*s + r == n, 0 <= r <= 2*s. """
s = isqrt(n)
return s, n - s*s
def csqrtrem(n):
""" For n > 0, return s, r satisfying n + s*s == r, 0 <= r <= 2*(s-1). """
s = 1 + isqrt(n-1)
return s, s*s - n
def factor(n):
""" Attempt to use Hart's algorithm to find a factor of n. """
for i in count(start=1):
s, m = csqrtrem(n*i)
t, r = isqrtrem(m)
if not r:
return gcd(n, s-t)
----------
_______________________________________
Python tracker <rep...@bugs.python.org>
<https://bugs.python.org/issue46187>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe:
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
