Факторизация числа N = pq при простых p и q методом дискретного логарифмирования
Предложен метод разложения на множители числа N = pq, где p и q—простые, в виде решения задачи определения показателя степени в уравненииa a^x mod n =b. Показано, что предложенный метод и метод Ферма эквивалентны по вычислительной сложности, но число итераций для метода дискретного логарифмирования...
Збережено в:
| Опубліковано в: : | Электронное моделирование |
|---|---|
| Дата: | 2013 |
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2013
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/100859 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Факторизация числа N = pq при простых p и q методом дискретного логарифмирования / C.Д. Винничук, А.В. Жилин, В.Н. Мисько // Электронное моделирование. — 2013. — Т. 35, № 5. — С. 3-10. — Бібліогр.: 14 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-100859 |
|---|---|
| record_format |
dspace |
| spelling |
Винничук, С.Д. Жилин, А.В. Мисько, В.Н. 2016-05-27T19:24:39Z 2016-05-27T19:24:39Z 2013 Факторизация числа N = pq при простых p и q методом дискретного логарифмирования / C.Д. Винничук, А.В. Жилин, В.Н. Мисько // Электронное моделирование. — 2013. — Т. 35, № 5. — С. 3-10. — Бібліогр.: 14 назв. — рос. 0204-3572 https://nasplib.isofts.kiev.ua/handle/123456789/100859 511:003.26.09 Предложен метод разложения на множители числа N = pq, где p и q—простые, в виде решения задачи определения показателя степени в уравненииa a^x mod n =b. Показано, что предложенный метод и метод Ферма эквивалентны по вычислительной сложности, но число итераций для метода дискретного логарифмирования в [0,5 log₂N] раз меньше, чем для метода Ферма. Запропоновано метод розкладання на множники числа N=pq, де p і q— прості, у вигляді розв’язку задачі визначення показника ступеня в рівнянні a^x mod n =b. Показано, що за пропонований метод i метод Ферма є еквівалентними за обчислювальною складністю, але кількість ітерацій для методу дискретного логарифмування в [0,5 log₂N] разів менше, ніж для методу Ферма. The authors have proposed a method for factoring the number of the form N = pq, where p and q are simple, as the solution to the problem of determining the exponent in the equation a^x mod n =b. It is shown that the proposed method and the method of Fermat are equivalent in terms of computational complexity, but the number of iterations of the discrete logarithm is [0,5log₂N] times less than for the method of Fermat. ru Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України Электронное моделирование Математические методы и модели Факторизация числа N = pq при простых p и q методом дискретного логарифмирования Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Факторизация числа N = pq при простых p и q методом дискретного логарифмирования |
| spellingShingle |
Факторизация числа N = pq при простых p и q методом дискретного логарифмирования Винничук, С.Д. Жилин, А.В. Мисько, В.Н. Математические методы и модели |
| title_short |
Факторизация числа N = pq при простых p и q методом дискретного логарифмирования |
| title_full |
Факторизация числа N = pq при простых p и q методом дискретного логарифмирования |
| title_fullStr |
Факторизация числа N = pq при простых p и q методом дискретного логарифмирования |
| title_full_unstemmed |
Факторизация числа N = pq при простых p и q методом дискретного логарифмирования |
| title_sort |
факторизация числа n = pq при простых p и q методом дискретного логарифмирования |
| author |
Винничук, С.Д. Жилин, А.В. Мисько, В.Н. |
| author_facet |
Винничук, С.Д. Жилин, А.В. Мисько, В.Н. |
| topic |
Математические методы и модели |
| topic_facet |
Математические методы и модели |
| publishDate |
2013 |
| language |
Russian |
| container_title |
Электронное моделирование |
| publisher |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| format |
Article |
| description |
Предложен метод разложения на множители числа N = pq, где p и q—простые, в виде решения задачи определения показателя степени в уравненииa a^x mod n =b. Показано, что предложенный метод и метод Ферма эквивалентны по вычислительной сложности, но число итераций для метода дискретного логарифмирования в [0,5 log₂N] раз меньше, чем для метода Ферма.
Запропоновано метод розкладання на множники числа N=pq, де p і q— прості, у вигляді розв’язку задачі визначення показника ступеня в рівнянні a^x mod n =b. Показано, що за пропонований метод i метод Ферма є еквівалентними за обчислювальною складністю, але кількість ітерацій для методу дискретного логарифмування в [0,5 log₂N] разів менше, ніж для методу Ферма.
The authors have proposed a method for factoring the number of the form N = pq, where p and q are simple, as the solution to the problem of determining the exponent in the equation a^x mod n =b. It is shown that the proposed method and the method of Fermat are equivalent in terms of computational complexity, but the number of iterations of the discrete logarithm is [0,5log₂N] times less than for the method of Fermat.
|
| issn |
0204-3572 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/100859 |
| citation_txt |
Факторизация числа N = pq при простых p и q методом дискретного логарифмирования / C.Д. Винничук, А.В. Жилин, В.Н. Мисько // Электронное моделирование. — 2013. — Т. 35, № 5. — С. 3-10. — Бібліогр.: 14 назв. — рос. |
| work_keys_str_mv |
AT vinničuksd faktorizaciâčislanpqpriprostyhpiqmetodomdiskretnogologarifmirovaniâ AT žilinav faktorizaciâčislanpqpriprostyhpiqmetodomdiskretnogologarifmirovaniâ AT misʹkovn faktorizaciâčislanpqpriprostyhpiqmetodomdiskretnogologarifmirovaniâ |
| first_indexed |
2025-12-07T17:39:56Z |
| last_indexed |
2025-12-07T17:39:56Z |
| _version_ |
1850872112682631168 |