The Department of
MATHEMATICAL FOUNDATIONS OF INFORMATICS
is organizing a seminar under the project Algebraic and Geometric Data Protection Methods, KП-06-Н32/2-2019.
Talks will be delivered by:
Pascal Piperkov, PhD student, IMI – BAS
on:
Applications of Discrete Transformations for Calculating the Parameters of a Linear Code over compound finite field
Lyubomir Borisov, IMI – BAS
on:
An efficient algorithm for computing the parity of order of elliptic curves over Fp
Abstract: In cryptographic applications it is desirable to employ elliptic curves of very large prime order to keep the security on a highest possible level. There is an efficient algorithm which computes the order of a given elliptic curve of general type [1]. To our knowledge the complexity of that algorithm is O(log8 q) where q is the employed field order (although there are improvements like the SEA (Schoof-Elkies-Atkins) algorithm of lower complexity). After computing the order of such a curve, an appropriate efficient primality test will decide whether this order is prime. However, it might be advantageous in some situations (especially when carrying out a random search for suitable curves) to apply a faster preliminary test, e.g. such that determines the parity of their order without actually computing it. In this work, we establish some results in the aforesaid direction, proposing finally an algorithm for finding out the parity of order whose complexity is O(log3 p) for curves over Fp. The algorithm is based on criteria for irreducibility of cubic polynomials due to L. E. Dickson [2].
REFERENCES
[1] R. Schoof, ”Counting points on elliptic curves over finite fields”, Journal de theorie des nombres de Bordeaux ´ , vol. 7(1), pp. 219–254, 1995.
[2] L. E. Dickson, ”Criteria for the irreducibility of functions in a finite field”, Bull. Amer. Math. Soc., vol. 13(1), pp. 1–8, 1906.
The seminar will be held on 09 February (Tuesday) 2021, at 11:00 am in Room 578 of IMI.
For online participation:
https://us02web.zoom.us/j/85138863398?pwd=NWpxdDRmc0wxdk1YMzBhT0YzWGFCQT09
Meeting ID: 851 3886 3398
Passcode: 046811