Elliptic Curve Method Using Complex Multiplication Method AIKAWA, Yusuke; NUIDA, Koji; SHIRASE, Masaaki
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences,
2019/01/01, 2019-1-1, 20190101, Letnik:
E102.A, Številka:
1
Journal Article
Recenzirano
Odprti dostop
In 2017, Shirase proposed a variant of Elliptic Curve Method combined with Complex Multiplication method for generating certain special kinds of elliptic curves. His algorithm can efficiently ...factorize a given composite integer when it has a prime factor p of the form 4p=1+Dv2 for some integer v, where -D is an auxiliary input integer called a discriminant. However, there is a disadvantage that the previous method works only for restricted cases where the class polynomial associated to -D has degree at most two. In this paper, we propose a generalization of the previous algorithm to the cases of class polynomials having arbitrary degrees, which enlarges the class of composite integers factorizable by our algorithm. We also extend the algorithm to more various cases where we have 4p=t2+Dv2 and p+1-t is a smooth integer.
The Kalray MPPA-256 processor is based on a recent low-energy manycore architecture. In this article, we investigate its performance in multiprecision arithmetic for number-theoretic applications. We ...have developed a library for modular arithmetic that takes full advantage of the particularities of this architecture. This is in turn used in an implementation of the ECM, an algorithm for integer factorization using elliptic curves. For parameters corresponding to a cryptanalytic context, our implementation compares well to state-of-the-art implementations on GPU, while using much less energy.
ECM using Edwards curves BERNSTEIN, DANIEL J.; BIRKNER, PETER; LANGE, TANJA ...
Mathematics of computation,
04/2013, Letnik:
82, Številka:
282
Journal Article
Recenzirano
Odprti dostop
This paper introduces EECM-MPFQ, a fast implementation of the elliptic-curve method of factoring integers. EECM-MPFQ uses fewer modular multiplications than the well-known GMP-ECM software, takes ...less time than GMP-ECM, and finds more primes than GMP-ECM. The main improvements above the modular-arithmetic level are as follows: (1) use Edwards curves instead of Montgomery curves; (2) use extended Edwards coordinates; (3) use signed-sliding-window addition-subtraction chains; (4) batch primes to increase the window size; (5) choose curves with small parameters and base points; (6) choose curves with large torsion.
This paper describes carry-less arithmetic operations modulo an integer 2^M-1 in the thousand-bit range, targeted at single instruction multiple data platforms and applications where overall ...throughput is the main performance criterion. Using an implementation on a cluster of PlayStation 3 game consoles a new record was set for the elliptic curve method for integer factorization.
Integer Number Crunching on the Cell Processor Hsieh-Chung Chen; Chen-Mou Cheng; Shih-Hao Hung ...
2010 39th International Conference on Parallel Processing,
2010-Sept.
Conference Proceeding
We describe our implementation of the Elliptic Curve Method (ECM) of integer factorization on the Cell processor. ECM is the method of choice for finding medium-sized prime factors, e.g., between 2 ...30 and 2 100 . A good ECM implementation is of paramount importance for evaluating the security of cryptosystems like RSA because it is a critical step in the modern versions of the Number Field Sieves (NFS), currently the most efficient cryptanalysis technique against RSA. We use ECM as a benchmark to understand how the performance of integer number crunching applications can benefit from several architectural design features of the Cell including wide arithmetic pipeline, auxiliary pipeline for handling managerial tasks, and large on-die memory per thread of execution. As a result, our ECM implementation on the PowerXCell 8i Cell processor outperforms all previously published implementations on other hardware platforms including graphics processing units (GPUs). For example, compared with the best published result on an NVIDIA GTX 295 graphics card, ours is more than three times faster on absolute basis. This is in spite of the fact that GPUs have greater raw number-crunching capability, not to mention that the Cell consumes less power and hence delivers much better performance per watt.
The aim of this paper is to describe and analyze new approach in solving factorization problem based on the fuse of elliptic curves and machine learning theories. This idea is considered due to high ...importance of this question and great perspective of such approach.
PDF
