x^2 mod N = 1 ?
x > 1
x < N-1
тут все условия и ограничения
для некоторго N надо найти одно или более X удовлетворяющих условию
а Вы не верно истолковали суть операции «остаток от деления»
x^2=k*N+1 в этой записи k так же не известное
пример
11*11 mod 15 = 1 ( 11*11 = 121 = 8*15+1 )
при этом 15 = 3*5 для целых и не может быть представлено в виде (x+1)*(x-1) с целым значением X
другой вопрос что не для любого N будут существовать решения для этих ограничений
x^2 mod N = x ?
x > 1
x < N-1
так же может быть рассмотрено
пример
6*6 mod 15 = 6 (6*6 = 36 = 2*15+6)
Владимиру:
для примера 11*11 % 15 = 1
% — это mod в стиле C
так вот, можно записать
121 = 12*10 + 1
но тогда
12*10=120=8*15
8 не известная величина, пока мы не знаем ответа 11 (или 10*12, не важно)
для N = 15 существует еще одно решение
4*4 % 15 = 16 % 15 = 1
так что ошибка в Ваших рассуждениях, а исходный вопрос содержит всю информацию о проблеме
Владимиру:
в случае факторизации задача вырождается в тривиальную,
только вот сама факторизация для больших чисел не приемлимо трудоемкая )))
меня интересовала точка зрения математиков на возможные пути решения
ps у Вас явные проблемы с самооценкой )))
тут есть психологи, обратитесь
|
|||||||||||||||||
|
||||||||||||
|
||||||||||||
|
|||||||||||
|
|
|
Похожие вопросы |