Хочу тестировать простые числа (BigInteger) для ключей этим тестом.
Согласно формуле, надо возводить в степень, которая этот самый BigInteger.
Формула: ((S * S) — 2) mod ((2 в степени P) — 1)
S и P — BigInteger

Есть мысли как модифицировать алгоритм, чтобы избежать возведения в BigInteger?

Здравствуйте, tapatoon, Вы писали:

T>Хочу тестировать простые числа (BigInteger) для ключей этим тестом.
T>Согласно формуле, надо возводить в степень, которая этот самый BigInteger.
T>Формула: ((S * S) — 2) mod ((2 в степени P) — 1)
T>S и P — BigInteger

T>Есть мысли как модифицировать алгоритм, чтобы избежать возведения в BigInteger?

Сори, если косячу, нифига не математик, но возникли такие вопросы:

1. А формула точно правильная ?? В вики написано , то есть формула рекурсивная. У тебя на рекурсию не похоже.
2. Ну и потом, ну узнаешь ты что

(2 в степени P) - 1

— простое. Но из этого никак не следует, что P — простое.

Здравствуйте, Jack128, Вы писали:

J>1. А формула точно правильная ?? В вики написано Image: 8e5e1f907d128b278f05db9de7333f353939a8d0 , то есть формула рекурсивная. У тебя на рекурсию не похоже.
Я привёл одну итерацию, для тех кому лень в вики лезть)

J>2. Ну и потом, ну узнаешь ты что
J>

J>(2 в степени P) - 1
J>

J> — простое. Но из этого никак не следует, что P — простое.
Это часть теста Baillie–PSW

Здравствуйте, tapatoon, Вы писали:

T>Есть мысли как модифицировать алгоритм, чтобы избежать возведения в BigInteger?
Я не вникал во всё, но как я вижу, надо посчитать "(2 в степени P) — 1", что в двоичном представлении это просто P штук единичек.

Здравствуйте, ·, Вы писали:

·>Я не вникал во всё, но как я вижу, надо посчитать "(2 в степени P) — 1", что в двоичном представлении это просто P штук единичек.
P примерно такое
{19584106937020209507252196043297899606150639594416573557601370358302595836899772763205901129028954253483656445869547157319442256987763485808630622731204702607725304393672091646626749217866856236614781071343335368281674035542300870799724013621718522337194406278051898707772888933820787591547643270817723404207636919984151269871568007568822372805185851967813940320287551137630460923721251805035039852013906842135318027582470859284202772189656126810755021790465171190932742377989915465879887469418270460930383147520271548662431286278669215961025807979940711940934567245768381839828712412737383163503304221271112074852003}

Здравствуйте, tapatoon, Вы писали:

T>·>Я не вникал во всё, но как я вижу, надо посчитать "(2 в степени P) — 1", что в двоичном представлении это просто P штук единичек.
T>P примерно такое
Ах, ну так тебе значит надо не просто в степень P возвести, а использовать результат в делении по модулю. И в той же вики написано:

Эффективный алгоритм деления по модулю числа Мерсенна на компьютере (фактически сводящийся к нескольким операциям битового сдвига) дает следующая теорема...

. Осталось разобраться в этой теореме.

Здравствуйте, tapatoon, Вы писали:

T>·>Я не вникал во всё, но как я вижу, надо посчитать "(2 в степени P) — 1", что в двоичном представлении это просто P штук единичек.
T>P примерно такое
T>{19584106937020209507252196043297899606150639594416573557601370358302595836899772763205901129028954253483656445869547157319442256987763485808630622731204702607725304393672091646626749217866856236614781071343335368281674035542300870799724013621718522337194406278051898707772888933820787591547643270817723404207636919984151269871568007568822372805185851967813940320287551137630460923721251805035039852013906842135318027582470859284202772189656126810755021790465171190932742377989915465879887469418270460930383147520271548662431286278669215961025807979940711940934567245768381839828712412737383163503304221271112074852003}
Вам явно нужны другие методы для такого p
https://www.mersenne.org/primes/