OFFSET
1,3
COMMENTS
Over the rationals Q there is for each prime p up to isomorphism a unique quaternion algebra B_p that is ramified exactly at the infinite place and p. B_p can be written in the form (-p,-q) where q is a positive integer.
More precisely (cf. Pizer p. 368) for q one can take: 1 if p=2 or p==3 (mod 4) and 2 if p==5 (mod 8). In the remaining case p==1 (mod 8) one can take q a prime such that (q/p)=-1, i.e., q is a nonquadratic residue mod p, and q==3 (mod 4). Due to Chebotarev density theorem such q do exist (cf. Eisenträger et al. p. 341) and can be effectively bounded (cf. Lagarias et al. p. 272 for the original result or Ahn et al. p. 1 for an explicit result). Under GRH one can bound q by O((log(p))^2) (cf. Eisenträger et al. p. 341).
For given p there are infinitely many such admissible q as any admissible q may be replaced by q*k^2 for any integer k. One can prove that the least admissible q is always of the form stated in Pizer.
The maximal orders in the quaternion algebra B_p correspond precisely to the endomorphism rings of supersingular elliptic curves defined over F_(p^2) the finite field with p^2 elements. They are under current research in connection with supersingular isogeny cryptosystems that are candidates for post-quantum cryptography (cf. Eisenträger et al. p. 336 f. for the current state or De Feo et al. p. 19 ff. for the original proposal of the public key exchange protocol).
LINKS
Robin Visser, Table of n, a(n) for n = 1..10000
Jeoung-Hwan Ahn, Soun-Hi Kwon, Explicit upper bound for the least prime ideal in the Chebotarev density theorem, arXiv:1807.00508 [math.NT], 2018, to appear at Annales de l'Institut Fourier.
L. De Feo, D. Jao, (2011), Towards Quantum-Resistant Cryptosystems from Supersingular Elliptic Curve Isogenies. In: Yang BY. (eds) Post-Quantum Cryptography. PQCrypto 2011. Lecture Notes in Computer Science, vol 7071, Springer, Berlin, Heidelberg.
K. Eisenträger, S. Hallgren, K. Lauter, T. Morrison, C. Petit, (2018), Supersingular Isogeny Graphs and Endomorphism Rings: Reductions and Solutions. In: Nielsen J., Rijmen V. (eds) Advances in Cryptology - EUROCRYPT 2018. EUROCRYPT 2018. Lecture Notes in Computer Science, vol 10822, Springer, Cham.
J. C. Lagarias, H. L. Montgomery and A. M. Odlyzko, A bound for the least prime ideal in the Chebotarev Density Theorem. Invent Math (1979) 54: 271.
A. Pizer, An algorithm for computing modular forms on Gamma_0(N). J. Algebra, 64 (2) (1980), pp. 340-390
FORMULA
The criterium of Pizer described above gives a compact formula.
EXAMPLE
for n=43 the a(43)=1 as the 43rd prime is 191 (cf. A000040) and 191==3 (mod 4);
for n=44 the a(44)=11 as the 44th prime is 193 (cf. A000040), 193==1 (mod 8) and the least prime q==3 (mod 4) that is a nonquadratic residue mod 193 is 11;
for n=45 the a(45)=2 as the 45th prime is 197 (cf. A000040) and 197==5 (mod 8).
PROG
(Magma)
n:=1000;
quatAlgRamAtInftyPMinQ := function(p)
q:=3;
while true do
if RamifiedPrimes(QuaternionAlgebra<Rationals()|-p, -q>) eq [p] then
return q;
end if;
q:=q+1;
end while;
end function;
[q: p in PrimesUpTo(n)| true where q is case<(p mod 8)|2:1, 3:1, 7:1, 5:2, 1:quatAlgRamAtInftyPMinQ(p), default:0>];
(Magma)
n:=1000;
pizerCondPMinQ := function(p)
q:=3;
while true do
if ((q mod 4) eq 3) and (LegendreSymbol(q, p) eq -1) then
return q;
end if;
q:=NextPrime(q);
end while;
end function;
[q: p in PrimesUpTo(n)| true where q is case<(p mod 8)|5:2, 1:pizerCondPMinQ(p), default:1>];
CROSSREFS
KEYWORD
nonn
AUTHOR
Thomas Preu, Nov 04 2018
STATUS
approved