Lenstra H.W. — Development of the Number Field Sieve :: Электронная библиотека попечительского совета мехмата МГУ

Главная Ex Libris Книги Журналы Статьи Серии Каталог Wanted Загрузка ХудЛит Справка Поиск по индексам Поиск Форум

Авторизация

Поиск по указателям

Lenstra H.W. — Development of the Number Field Sieve

Обсудите книгу на научном форуме

Нашли опечатку?
Выделите ее мышкой и нажмите Ctrl+Enter

Название: Development of the Number Field Sieve

Автор: Lenstra H.W.

Аннотация:

The number field sieve is an algorithm for finding the prime factors of large integers. It depends on algebraic number theory. Proposed by John Pollard in 1988, the method was used in 1990 to factor the ninth Fermat number, a 155-digit integer. The algorithm is most suited to numbers of a special form, but there is a promising variant that applies in general. This volume contains six research papers that describe the operation of the number field sieve, from both theoretical and practical perspectives. Pollards original manuscript is included. In addition, there is an annotated bibliography of directly related literature.

Язык:

Рубрика: Математика/

Статус предметного указателя: Готов указатель с номерами страниц

ed2k: ed2k stats

Издание: 1st edition

Год издания: 1993

Количество страниц: 139

Добавлена в каталог: 02.07.2008

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID

Предметный указатель

-smooth      13 16
      19 114
      123
      2 19 114
      123
$l_{P}$       59 61 63—66 89
$L_{x}[v,\lambda]$       11 31 51
      19 114 123
      2 19 114
      123
      123
$p\pm 1$ method      120
-smooth      57
$\check{C}$ ebotarev density theorem      70 72 74
$\{e\}$       106 108 112
ABRA      105 114
Address      iv 3 10 42 49 94 102 126
AFB      105 106 108
Alg-smooth      114
algbase      105 108
Algebraic geometry      127
Algebraic number theory      14 22 57 59
Algebraic sieve      27 57
Algorithm      7—8 14—20 43—44 80 85—86 99 101—102 109 110
Analytic number theory      76—79
Auxiliary polynomial      13 54 86—87 90 104—105 107 124
Base method      54 107
Basically smooth      106
Basis reduction      24 30 39 45 67 73 75 87 113
Bibliography      see “References”
Bimodal polynomials method      13
Character column      51 67 71 104 115
Chinese remainder theorem      64 66 97 98 119 124
Class group relations method      12 30 31 78
Combination of congruences      53
Composition factors      65 89
Conjecture      80 81
Continued fraction method      12 30 52
Coordinate recurrence algorithm      80—84 86 116
cosqrt      105 116
Cubic sieve      12 13
CYCLE      18 34 116
data flow      104 105
Degree      13 15 32 58 63 71 98 104 124
Dependency      14 22 39 56 80 86 115 116
Dickman’s $\rho$ function      44
Discrete logarithm problem      2 3 13 52 61
Discriminant      22 38 39 54 62 88 96 105 118
Double large primes      34
E-mail address, iv      3 42 94 102 126
Efficiency      27
Electronic mail      35
Elimination over $\mathbf{Z}$       38
Elliptic curve method      12 30 35 78 86 104 120
Elliptic curve primality test      120
Elliptic curve smoothness test      25 78
example      10 34—37 49 120—124
Exceptional prime ideal      23
Exponential time      12
Factor base      7 14 16 47 56 69 95 108 113
Fast multiplication      71 72 75 84 97 100 101 124
Fermat number, ninth, v      1 2 11 33 37 44 50 92 121 123
Fermat number, seventh      1 7 8 34 43 46 49
First degree prime ideal      16 21 58 88 89
Free relation      7 20 30 47 124
Front cover      127—128
Full relation      17
Fuzz factor      111
Gauss      105 116
Gaussian elimination      37 116
Gaussian integers      4 13
General integer      51 81
General number field sieve      50—94 103—126
GNFS      103
Group theory      74 101
Heuristic analysis      31 77
Heuristic principle      77
Homogeneous polynomial      84—92 107
illustration      127—128
implementation      9 11—42 48 103 126
Inert prime      108 116 118
Infinite prime      73
IPB      105 106 108 116 118 120
irred      105 108
Irreducibility      15 54 71 72 88 101 108
ISP      44
Jacobi sum primality test      120 121
Jacobi symbol routine      115

Jordan — H $\ddot{o}$ lder theorem      59 63
Large prime      7 17 18 34 43 92 104 113 114
Large prime bound      17 28 106
Large prime ideal      17 18
Lattice sieve      43—49 92 104 109—110
Legendre symbol      68 70 85 115
Length      63 74
Line method      109 110
Linear algebra over $\mathbf{F}_{2}$       14 15 56 67 68 116
Linear algebra over $\mathbf{Z}$       24 38 67
MasPar      103 112
Mat      105 115
Matrix reduction      see “Gaussian elimination”
Medium prime      43
Mersenne number      121
Modular arithmetic      98 99
Multi-field approach      2 33 36 40 52
Multiplier bound      21
newmat      105 115
Newton iteration      72 73 97
Norm      5 16 22 43 57 58 63 97 105 118
Number field      15 53 63 95 105
Number field sieve      passim
Obstruction      60 67 89
Order      63 88
OUT      105 112 114
Parameter choice      28 31 36 47 75 84 90 106 120 121 125
Partial relation      17
Pe      121
Plane method      109 110
Pollard’s $\rho$ method      104
POLY      104 105 106
Polynomial      see “Auxiliary polynomial”
Polynomial time      12
Positive square root method      95—102 104 116—120
Prec-smooth      113 114
Prime      5 58
Prime element      16 23
Prime ideal      16 58
Prime ideal factorization      16 38 59 63 97
Prime power      14 80 104
Product representation      25
Projective line      85
Projective polynomial      104 106
pulls      105 112
QCB      105 106 108 115 118
QS      103
Quadratic character      40 58 67—70 89 96 115
Quadratic sieve      7 12 30 35 51 52 53 78 103 112 120 124
Random squares method      12 30 31 52 78
Rat-smooth      114
Rational sieve      7 26 55
Record      121
References, v      1—3 10 40—42 49 92—94 102 125-126
Relation      14 104
Report      27 112 123
RFB      105 106 108
Ring homomorphism      15 23 53 59 88 95 119
Ring of integers      22 38 39 40 50 57 59 63 89
run time      9 12 13 30—33 40 51 75 77 80—84 100—101 111—112
Scheme      128
Search bound      21
Search for prime elements      23
sgauss      105 116
Sieve      7 25—28 45—46 55—60 108-114
Sieve-smooth      108
Sieving by rows      46 110 112
Sieving by vectors      46 110
SIMD      103 112
Simple module      65
Singular integers      2
Small prime      43
Smooth      12 16 95 104
Smoothness bound      16 17
Smoothness probability      31 76—78 87
SNFS      103
SOLNS      105 116
Special number field sieve      11—42 51 103
Special prime      43 109 113
Spectrum      127
Square root      40 53 70—76 95—102 116—120 124
Trial division      8 12 27 86 114
Two-thirds algorithm      30 31 78
Unique factorization      4 15 22 24 40 50 57 63
UNIT      5 16 17 20 24 29 30 50
Unit contribution      29 34 35
Wanted list      14
Would be smooth      78 84

О проекте