Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.
%I #27 Sep 30 2023 20:07:32
%S 1,1,2,1,1,2,3,1,1,2,1,2,3,1,1,2,1,2,1,1,7,1,1,3,7,2,1,1,2,3,1,1,3,1,
%T 2,1,2,1,1,2,1,2,1,11,2,1,1,1,1,2,3,1,7,1,3,1,2,1,2,3,1,2,1,1,7,2,1,
%U 11,1,2,3,1,1,2,1,1,2,2,3,7,1,2,1,7,1,1,3,11,2,1,1,1,1,1,1,1,2,3,1,2,1,2,1,3,1,7,1,3,1,7,1,2,3,1,1,3,1,1,2,1,2,11,2,1,1,2,2,1
%N Minimal positive integers q_n such that for the n-th prime p_n the quaternion algebra (-p_n,-q_n) is ramified exactly at infinity and p_n.
%C 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.
%C 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).
%C 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.
%C 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).
%H Robin Visser, <a href="/A318288/b318288.txt">Table of n, a(n) for n = 1..10000</a>
%H Jeoung-Hwan Ahn, Soun-Hi Kwon, <a href="https://arxiv.org/abs/1807.00508">Explicit upper bound for the least prime ideal in the Chebotarev density theorem</a>, arXiv:1807.00508 [math.NT], 2018, to appear at Annales de l'Institut Fourier.
%H L. De Feo, D. Jao, (2011), <a href="https://doi.org/10.1007/978-3-642-25405-5_2">Towards Quantum-Resistant Cryptosystems from Supersingular Elliptic Curve Isogenies</a>. In: Yang BY. (eds) Post-Quantum Cryptography. PQCrypto 2011. Lecture Notes in Computer Science, vol 7071, Springer, Berlin, Heidelberg.
%H K. Eisenträger, S. Hallgren, K. Lauter, T. Morrison, C. Petit, (2018), <a href="https://eprint.iacr.org/2018/371.pdf">Supersingular Isogeny Graphs and Endomorphism Rings: Reductions and Solutions</a>. In: Nielsen J., Rijmen V. (eds) Advances in Cryptology - EUROCRYPT 2018. EUROCRYPT 2018. Lecture Notes in Computer Science, vol 10822, Springer, Cham.
%H J. C. Lagarias, H. L. Montgomery and A. M. Odlyzko, <a href="https://doi.org/10.1007/BF01390234">A bound for the least prime ideal in the Chebotarev Density Theorem</a>. Invent Math (1979) 54: 271.
%H A. Pizer, <a href="https://doi.org/10.1016/0021-8693(80)90151-9">An algorithm for computing modular forms on Gamma_0(N)</a>. J. Algebra, 64 (2) (1980), pp. 340-390
%F The criterium of Pizer described above gives a compact formula.
%e for n=43 the a(43)=1 as the 43rd prime is 191 (cf. A000040) and 191==3 (mod 4);
%e 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;
%e for n=45 the a(45)=2 as the 45th prime is 197 (cf. A000040) and 197==5 (mod 8).
%o (Magma)
%o n:=1000;
%o quatAlgRamAtInftyPMinQ := function(p)
%o q:=3;
%o while true do
%o if RamifiedPrimes(QuaternionAlgebra<Rationals()|-p,-q>) eq [p] then
%o return q;
%o end if;
%o q:=q+1;
%o end while;
%o end function;
%o [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>];
%o (Magma)
%o n:=1000;
%o pizerCondPMinQ := function(p)
%o q:=3;
%o while true do
%o if ((q mod 4) eq 3) and (LegendreSymbol(q,p) eq -1) then
%o return q;
%o end if;
%o q:=NextPrime(q);
%o end while;
%o end function;
%o [q: p in PrimesUpTo(n)| true where q is case<(p mod 8)|5:2,1:pizerCondPMinQ(p),default:1>];
%Y Uses A000040 as a(n) depends on the n-th prime number.
%K nonn
%O 1,3
%A _Thomas Preu_, Nov 04 2018