|
|
Sieving in factoring algorithms
Staško, Samuel ; Příhoda, Pavel (advisor) ; Jedlička, Přemysl (referee)
The quadratic sieve and the number field sieve are two traditional factoring methods. We present here a principle of operation of both these algorithms, focusing mainly on the calculation of asymptotic complexity. The greatest emphasis is placed on the analysis of the sieving phase. However, the main goal of this work is to describe various modi- fications, estimate their time complexity and compare their practical usability with the basic versions. Apart from several well-known variants, we present our own proposals of both quadratic and number field sieve and analyze their advantages and disadvantages in detail. 1
|
|
|
Sieving in factoring algorithms
Staško, Samuel ; Příhoda, Pavel (advisor) ; Jedlička, Přemysl (referee)
The quadratic sieve and the number field sieve are two traditional factoring methods. We present here a principle of operation of both these algorithms, focusing mainly on the calculation of asymptotic complexity. The greatest emphasis is placed on the analysis of the sieving phase. However, the main goal of this work is to describe various modi- fications, estimate their time complexity and compare their practical usability with the basic versions. In addition, we present our own variant of the quadratic sieve, which has relatively large advantages in some areas compared to other known suggestions. 1
|
|
|
Cubic and biquadratic reciprocity
Staško, Samuel ; Příhoda, Pavel (advisor) ; Krásenský, Jakub (referee)
The main motivation for studying cubic and biquadratic reciprocity is to de- cide, whether the congruences x3 ≡ a (p) or x4 ≡ a (p), where a ∈ Z, p prime, have any integer solution. The core of this thesis will be to prove the laws of cubic and biquadratic reciprocity through gradually built theory in the rings of Eisen- stein and Gaussian integers. In addition, for both of these theorems, we will take a closer look at the special cases, in which they cannot be used. This will lead us to the derivation of the supplement to the law of cubic (or biquadratic) re- ciprocity. Finally, we will show how these results can be applied to the problem of solvability of mentioned congruences. 1
|
guest ::
