Прогресс в теории простых чисел и методы шифрования

[Dmitriy40]

B3LYP в сообщении #1732249 писал(а):

p=20, q=25
n=500 f=456
e=11 d=83

Пример некорректен: для данных n,e указанное d - неправильное ибо $(d \cdot e) \bmod \varphi(n) = 113$ вместо правильного $1$.
Кроме того, p=20 и q=25 и не взаимно простые.

Но даже взяв правильное d=91 не получим правильной передачи. Беда. Похоже n должно быть бесквадратным (т.е. p и q взаимно простыми, но могут быть составными). Например n=11#=2310 вполне себе подходит, даже при том что p=2*3*5=30 и q=7*11=77 оба составные.

И не надо приводить длинные числа, вполне достаточно их остатка по модулю n.

[B3LYP]

Dmitriy40
Так. Я посмотрел ещё раз в вики: $\varphi(n)=(p-1) \cdot (q-1)$. Т.е. в данном случае $\varphi(n)=(20-1) \cdot (25-1)=19 \cdot 24 = 456$.

$e \cdot d = 11 \cdot 83 = 913$
$913 \mod 456 = 1$

[Dmitriy40]

B3LYP в сообщении #1732260 писал(а):

Я посмотрел ещё раз в вики: $\varphi(n)=(p-1) \cdot (q-1)$.

Это верно только для простых p и q! А Вы хотите взять не простые p и/или q, для составных чисел функция Эйлера вычисляется по другому!.

-- добавлено через 3 минуты --

B3LYP
$\varphi(500)=\varphi(2^2 5^3)=\varphi(2^2)\varphi(5^3)=(2^2-2^1)(5^3-5^2)=(2)(100)=200\ne456$

[wrest]

B3LYP в сообщении #1732260 писал(а):

Так. Я посмотрел ещё раз в вики:

Вы же функцию Эйлера тут осваиваете, уже 2 месяца :

B3LYP в сообщении #1726517 писал(а):

хочется самому отвелосипедить функцию Эйлера

[B3LYP]

Dmitriy40

Спасибо, подразобрался.

Dmitriy40 в сообщении #1732255 писал(а):

Но даже взяв правильное d=91 не получим правильной передачи. Беда. Похоже n должно быть бесквадратным (т.е. p и q взаимно простыми, но могут быть составными). Например n=11#=2310 вполне себе подходит, даже при том что p=2*3*5=30 и q=7*11=77 оба составные.

Да, похоже на то. Вот два примера:

(Оффтоп)

p=6 q=35 n=210 f=48
e=11 d=35
m=135
135^11=271438504226343896484375
271438504226343896484375 mod 210 = 165
165^35=409202282478717852259700467690271555918554637759745403309352695941925048828125
409202282478717852259700467690271555918554637759745403309352695941925048828125 mod 210 = 135

(Оффтоп)

p=12 q=35 n=420 f=96
e=11 d=35
m=2

2^11=2048
2048 mod 420=368
368^35=637784049366552929672610310568691120302253094297420830109706803069604487596215835329298432

637784049366552929672610310568691120302253094297420830109706803069604487596215835329298432 mod 420 = 212

Ежели кому надо, могу закодить такой расчёт для миллионов случаев со случайными p и q, чтобы окончательно убедиться.

Dmitriy40 в сообщении #1732255 писал(а):

И не надо приводить длинные числа, вполне достаточно их остатка по модулю n.

Разве мне не надо всё приводить, чтобы можно было скопировать и проверить?

[Dmitriy40]

B3LYP в сообщении #1732508 писал(а):

Разве мне не надо всё приводить, чтобы можно было скопировать и проверить?

Зачем приводить $m^e$ если можно привести сразу $(m^e) \bmod n$, ведь $n$ и так приведено отдельно и каждый желающий проверить легко вычислит второе выражение без первого? Для проверки достаточно p,q,e,m (или p,q,d,m, или n,e,m, или n,d,m), всё остальное легко вычисляется.

B3LYP в сообщении #1732508 писал(а):

Ежели кому надо, могу закодить такой расчёт для миллионов случаев со случайными p и q, чтобы окончательно убедиться.

Думаю это надо Вам, остальные и так понимают (или могут проверить и сами, как я). Да и миллионы p,q не нужны, достаточно перебрать все варианты взаимно простых пар меньших некоторого не слишком маленького (не меньше тысячи к примеру) порога. В PARI/GP например есть даже специальный цикл для перебора таких n (p и q же тогда вообще не нужны), называется forsquarefree() (кстати сразу выдаёт и разложение на простые множители), правда надо будет ещё исключить простые n, но это тоже просто.

[B3LYP]

wrest в сообщении #1732195 писал(а):

У меня вопрос: если брать случайные числа размером 300 байт, сколько в среднем у каждого из них простых делителей?
В среднем около 8

Вы не путаете? Я сейчас посчитал - для чисел от 900000 до 1000000 среднее число простых делителей 3.6984. Т.е. уже довольно много.

[wrest]

B3LYP в сообщении #1732681 писал(а):

Я сейчас посчитал - для чисел от 900000 до 1000000 среднее число простых делителей 3.6984. Т.е. уже довольно много.

Вы спрашивали про числа размером 300 байт (2400 бит), а проверяли на числах размером 20 бит. Это вы путаете.
Впрочем, вы же можете и проверить, да?

[Dmitriy40]

B3LYP в сообщении #1732681 писал(а):

Я сейчас посчитал - для чисел от 900000 до 1000000 среднее число простых делителей 3.6984. Т.е. уже довольно много.

А я посчитал и получил 2.92518.
А для чисел 900...999 среднее получилось 2.28. "Т.е. уже довольно много."(с)Вы. Считать ли первое число, около миллиона, неправильным на основании лишь второго, около тысячи? Ответ очевиден.

Для чисел почти 1млрд среднее 3.320476.
Для чисел почти 1трлн среднее 3.601435.
Для чисел около 1e15 среднее 3.820242.
Для чисел около 1e18 среднее 3.999847.
Очевидно что рост сильно медленный. И похоже ещё и замедляется.

[wrest]

Dmitriy40 в сообщении #1732692 писал(а):

Очевидно что рост сильно медленный.

Ага, рост как $\ln \ln n$

? log(log(10^6))
2.6257919144760108006156904062382413682
? log(log(10^12))
3.3189390950359561100329225276964179363
? log(log(10^800))
7.5186441729158830960908923216007972149
?

[mihaild]

wrest в сообщении #1732694 писал(а):

Ага, рост как $\ln \ln n$

Теорема Эрдеша-Каца как раз это и говорит (и даже уточняет, каким бывает отклонение).

[wrest]

mihaild в сообщении #1732695 писал(а):

Теорема Эрдеша-Каца
как раз это и говорит (и даже уточняет, каким бывает отклонение).

Да, и ещё есть небольшая поправка в плюс если считать с учётом степеней простых в разложении.
На этой теореме (в том числе) вроде бы основаны прикидки сколько "посторонних" простых попадёт в элементы цепочек в эквиделительных темах ( «Пентадекатлон мечты» и около), и соотвественно - сколько их заложить в "паттерн" через КТО чтобы ещё осталось столько места сколько надо.

[B3LYP]

Dmitriy40 в сообщении #1732692 писал(а):

А я посчитал и получил 2.92518.
А для чисел 900...999 среднее получилось 2.28. "Т.е. уже довольно много."(с)Вы. Считать ли первое число, около миллиона, неправильным на основании лишь второго, около тысячи? Ответ очевиден.

Откуда у нас вообще разница?
Я сейчас пересчитал. Для чисел 900...999 (всего 100 чисел) среднее число простых делителей 3.01.
Для чисел 9000...9999 (всего 1000 чисел) среднее число простых делителей 3.307.
Для чисел 90000...99999 (всего 10000 чисел) среднее число простых делителей 3.523.
Для чисел 900000...999999 (всего 100000 чисел) среднее число простых делителей 3.698.

[Dmitriy40]

B3LYP в сообщении #1732707 писал(а):

Откуда у нас вообще разница?
Я сейчас пересчитал. Для чисел 900...999 (всего 100 чисел) среднее число простых делителей 3.01.

А, Вы простые в степени учитываете больше одного раза, а я ровно один:

? s=0.0;for(x=900,999,s+=omega(x));s/100
%1 = 2.2800000000000000000000000000000000000
? s=0.0;for(x=900,999,s+=bigomega(x));s/100
%2 = 3.0100000000000000000000000000000000000

[B3LYP]

Dmitriy40 в сообщении #1732710 писал(а):

А, Вы простые в степени учитываете больше одного раза, а я ровно один:

Понятно. А не может быть такого, что восемь простых множителей для чисел размером 300 байт - это именно если учитывать по одному разу, а если по несколько как я - то будет уже не восемь а восемьдесят?