1 |
An Improvement of The Multiple Polynomial Quadratic SieveHou, Ya-Fang 25 August 2008 (has links)
Large integer factoring problem is a difficult computing problem. The security of many public-key cryptograohy system depend on the large interger factoring problem. Dr. Guan implement ¡uThe Multiple Polynomail Quadratic Sieve Algorithm¡v and name the program ¡uGQS¡v. The program successfully factor RSA-130 interger in 2004. It can reduce the time of sieving that the MPQS algorithm retain the smooth number with one or two prime. But finally the size of factor basis is large. We use some of the prime retained by the MPQS algorithm to match with the smooth number and reduce the size of factor basis. And then we can reduce the time of factoring. In this paper, we implement our idea in a AIX server and the result of this paper can be a suggestion of the improvement of MPQS.
|
2 |
Distributed System for Factorisation of Large NumbersJohansson, Angela January 2004 (has links)
<p>This thesis aims at implementing methods for factorisation of large numbers. Seeing that there is no deterministic algorithm for finding the prime factors of a given number, the task proves rather difficult. Luckily, there have been developed some effective probabilistic methods since the invention of the computer so that it is now possible to factor numbers having about 200 decimal digits. This however consumes a large amount of resources and therefore, virtually all new factorisations are achieved using the combined power of many computers in a distributed system. </p><p>The nature of the distributed system can vary. The original goal of the thesis was to develop a client/server system that allows clients to carry out a portion of the overall computations and submit the result to the server. </p><p>Methods for factorisation discussed for implementation in the thesis are: the quadratic sieve, the number field sieve and the elliptic curve method. Actually implemented was only a variant of the quadratic sieve: the multiple polynomial quadratic sieve (MPQS).</p>
|
3 |
Distributed System for Factorisation of Large NumbersJohansson, Angela January 2004 (has links)
This thesis aims at implementing methods for factorisation of large numbers. Seeing that there is no deterministic algorithm for finding the prime factors of a given number, the task proves rather difficult. Luckily, there have been developed some effective probabilistic methods since the invention of the computer so that it is now possible to factor numbers having about 200 decimal digits. This however consumes a large amount of resources and therefore, virtually all new factorisations are achieved using the combined power of many computers in a distributed system. The nature of the distributed system can vary. The original goal of the thesis was to develop a client/server system that allows clients to carry out a portion of the overall computations and submit the result to the server. Methods for factorisation discussed for implementation in the thesis are: the quadratic sieve, the number field sieve and the elliptic curve method. Actually implemented was only a variant of the quadratic sieve: the multiple polynomial quadratic sieve (MPQS).
|
4 |
Paralelizace faktorizace celých čísel z pohledu lámání RSA / Parallelization of Integer Factorization from the View of RSA BreakingBreitenbacher, Dominik January 2015 (has links)
This paper follows up the factorization of integers. Factorization is the most popular and used method for RSA cryptoanalysis. The SIQS was chosen as a factorization method that will be used in this paper. Although SIQS is the fastest method (up to 100 digits), it can't be effectively computed at polynomial time, so it's needed to look up for options, how to speed up the method as much as possible. One of the possible ways is paralelization. In this case OpenMP was used. Other possible way is optimalization. The goal of this paper is also to show, how easily is possible to use paralelizion and thanks to detailed analyzation the source codes one can reach relatively large speed up. Used method of iterative optimalization showed itself as a very effective tool. Using this method the implementation of SIQS achieved almost 100 multiplied speed up and at some parts of the code even more.
|
5 |
Square Forms Factoring with SievesClinton W Bradford (10732485) 05 May 2021 (has links)
Square Form Factoring is an <i>O</i>(<i>N</i><sup>1/4</sup>) factoring algorithm developed by D. Shanks using certain properties of quadratic forms. Central to the original algorithm is an iterative search for a square form. We propose a new subexponential-time algorithm called SQUFOF2, based on ideas of D. Shanks and R. de Vogelaire, which replaces the iterative search with a sieve, similar to the Quadratic Sieve.
|
6 |
Integer Factorization on the GPU / Integer Factorization on the GPUPodhorský, Jiří January 2014 (has links)
This work deals with factorization, a decomposition of composite numbers on prime numbers and possibilities of its parallelization. It summarizes also the best known algorithms for factoring and most popular platforms for the implementation of these algorithms on the graphics card. The main part of the thesis deals with the design and implementation of hardware acceleration current fastest algorithm on the graphics card by using the OpenCL framework. Subsequently, the work provides a comparison of speeds accelerated algorithm implemented in this work with other versions of the best known algorithms for factoring, processed serially. In conclusion, the work discussed length of RSA key needed for safe operation without the possibility of breaking in real time interval.
|
Page generated in 0.0854 seconds