Аналіз ефективності методу факторизації на еліптичних кривих. Практика

Проблема факторизації безпосередньо пов'язана з визначенням криптостійкості RSA, яке базується на припущенні, що не існує швидких алгоритмів факторизації, які за короткий час дали б зламати код, а якщо через деякий час і вийде це зробити, то дані втратять свою актуальність. У цій статті ми протестуємо і зробимо висновки по одному з методів факторизації.

Читати далі →

Непрості прості числа: секрети таємного товариства ткачів

Непрості прості числа



Автор статті пропонує заглянути в те, що являють собою безлічі простих чисел, якщо поглянути на них геометричним чином. Це не професійна робота, а просте, любительське дослідження деяких цікавих закономірностей. Тому, в статті не буде складної математики, і ми не будемо забиратися глибоко в її нетрі.

Ймовірно, читачеві відомі багато проблем, пов'язані з простими числами. Їх розташування у множині натуральних чисел неочевидно. Великі прості числа важко знаходити, потрібно багато зусиль, щоб перевірити велике число на простоту. На цій труднощі засновані багато сучасні методи криптографії. Ми можемо легко перемножити та багатозначних простих числа, але знаючи результат знайти вихідні множники — дуже складне завдання.

Є безліч способів оптимізації, які набагато швидше простого перебору, проте навіть якщо оптимізація прискорить пошук в 10 разів, достатньо збільшити число на 2-3 десяткових знака (наприклад, в 100 раз), щоб уповільнити пошук в 10^100 раз.

Це і означає, що складність алгоритму є експоненціальною, і тому який би швидкий був суперкомп'ютер, ми можемо підібрати довжину числа ще більше, щоб таких суперкомп'ютерів знадобилося мільярд. Щоправда, варто уточнити ще раз: знаходити прості числа для перемноження при цьому стає так само все важче і важче.

До речі, математики не знайшли ні докази, ні спростування того, що не можна знайти алгоритм факторизації, складність якого не була б експоненціально залежить від довжини числа. А довівши або спростувавши це, можна, заодно, вирішити математичну проблему, відому як гіпотеза Рімана. За її доказ математичний інститут Клея обіцяє мільйон доларів.


Читати далі →

Факторизація і шифрування на еліптичній кривій

     Проблема факторизації складових натуральних чисел (сннч) багато століть утримує увагу фахівців різних теоретичних (наукових) і прикладних областях, таких як числові системи, обчислювальна математика і техніка, теорія чисел, інформаційна безпека, криптографія, та ін., і змушує їх докладати чималих зусиль до її позитивного й успішного вирішення. Тим не менше, проблема і сьогодні далека від її закриття, завершення. Автор пропонує до розгляду і прагне дати читачеві поняття про існуючі підходи до вирішення проблеми, що стали вже своєрідною класикою, привести критику і висловити схвалення чудовим знахідкам.
     У роботі викладається один з відомих підходів до вирішення задачі факторизації великих чисел (ЗФБЧ), що використовує математику еліптичних кривих (ЕК). Про цю математики, а точніше про техніку обчислень наведу цитату авторів [ 1 ] «Техніка, яка використовується в даний час при вивченні ЕК, є однією з найдосконаліших у всій математиці. Ми сподіваємося, що елементарний підхід цієї роботи спонукає читача до подальшого вивчення цієї живої і чарівною гілки теорії чисел. Є багато того, що варто вивчити, і багато роботи, яку треба виконати. „

Читати далі →