|
|
A373461
|
|
a(n) = s - t where s = ceiling(sqrt(n*i)), t = sqrt(m), and m = s^2 mod n, for the smallest positive integer i for which m is square.
|
|
1
|
|
|
1, 2, 1, 2, 1, 2, 3, 2, 3, 4, 5, 2, 7, 8, 3, 4, 9, 6, 11, 4, 3, 14, 15, 4, 5, 16, 3, 6, 19, 6, 21, 4, 9, 24, 5, 6, 25, 26, 9, 4, 29, 6, 31, 12, 5, 34, 35, 6, 7, 10, 9, 14, 39, 12, 5, 8, 9, 44, 45, 6, 47, 48, 7, 8, 5, 12, 51, 20
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
This is "s - t" in Hart's factoring algorithm.
The quantities found have s^2 - t^2 = (s-t)*(s+t) = n*i when n >= 3 and Hart notes that g = gcd(s-t, n) is a nontrivial factor of n (when n is composite).
|
|
REFERENCES
|
S. S. Wagstaff, Jr., The Joy of Factoring, AMS, 2013, pages 119-120.
|
|
LINKS
|
|
|
EXAMPLE
|
For n=9, i=1, s=ceiling(sqrt(9*1))=3 and m=0 then s-floor(sqrt(m))=3-0=3, so a(9)=3.
Also gcd(9, 3) gives a divisor of 3.
|
|
PROG
|
(Python)
from sympy.ntheory.primetest import is_square
from sympy.core.power import isqrt
def a(n):
i = 1
while True:
if is_square(m:=pow(s, 2, n)):
return s-isqrt(m)
i+=1
print([a(n) for n in range(1, 69)])
(PARI)
a(n) = my(i=1, s, t); while(!issquare((s=sqrtint((n*i)-1)+1)^2 % n, &t), i++); s-t;
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|