|
| |
|
|
A318288
|
|
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.
|
|
1
|
|
|
|
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, 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, 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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
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.
|
|
|
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
|
Uses A000040 as a(n) depends on the n-th prime number.
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
