cp's OEIS Frontend

A377059 a(n) is the smallest even r less than n-1 such that x^r = 1 (mod n) for the least x such that gcd(x,n)=1 for n >= 4 else 0.

%I A377059 #37 Nov 15 2024 01:09:27
%S A377059 0,0,0,2,2,2,2,2,6,4,2,2,6,6,4,4,8,6,6,4,6,10,2,2,20,4,18,6,14,4,6,8,
%T A377059 10,16,12,6,18,18,12,4,20,6,14,10,12,22,2,4,42,20,8,6,26,18,20,6,18,
%U A377059 28,2,4,10,30,6,16,12,10,22,16,22,12,10,6,12,18,20,18
%N A377059 a(n) is the smallest even r less than n-1 such that x^r = 1 (mod n) for the least x such that gcd(x,n)=1 for n >= 4 else 0.
%C A377059 This is essentially a part of Shor's algorithm.
%C A377059 While in Shor's algorithm the key step is to determine the period (or order) of x^r (mod n), based on finding the smallest even multiplicative order number r such that x^r = 1 (mod n) for a random x in order to factor a number n efficiently, in this algorithm we find such r for the least x coprime to n.
%C A377059 If this r is not even, it is discarded and the next number x is tried.
%C A377059 While in Shor's quantum algorithm the period search function runs in polynomial time, its classical counterpart runs in non-polynomial time.
%C A377059 Also a(n) is a divisor of the Euler's totient of n (A000010).
%H A377059 Robert Israel, <a href="/A377059/b377059.txt">Table of n, a(n) for n = 1..10000</a>
%H A377059 Wikipedia, <a href="https://en.wikipedia.org/wiki/Shor%27s_algorithm">Shor's algorithm</a>.
%F A377059 a(n) = gcd(a(n), A000010(n)) for n >= 3.
%p A377059 f:= proc(n) local x,r;
%p A377059   for x from 2 to n do
%p A377059     if igcd(x,n) <> 1 then next fi;
%p A377059     r:= numtheory:-order(x,n);
%p A377059     if r::even and r < n-1 then return r fi
%p A377059   od;
%p A377059   0
%p A377059 end proc:
%p A377059 map(f, [$1..100]); # _Robert Israel_, Nov 14 2024
%o A377059 (Python)
%o A377059 from sympy import gcd
%o A377059 from sympy.ntheory.residue_ntheory import n_order
%o A377059 def a(n):
%o A377059     for x in range(2, n):
%o A377059         if gcd(x, n) == 1:
%o A377059             r = n_order(x, n)
%o A377059             if r & 1 == 0 and r < n-1:
%o A377059                 return r
%o A377059     return 0
%o A377059 print([a(n) for n in range(1, 77)])
%Y A377059 Cf. A000010, A378028, A378029.
%K A377059 nonn,look
%O A377059 1,4
%A A377059 _Darío Clavijo_, Oct 14 2024