Как быстро посчитать M! mod N?

UbIvItS

Во-первых, в предыдущем сообщении вообще нет никаких вычислений символа Якоби.
Во-вторых, 10 действительно не является квадратом по модулю 91 (в частности также по модулю 7).

 

RElf

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

 

ссылка хорошая, а формулу (33) они конечно мелковато нарисовали.

 

мда.. заклинило меня на x^2-y^2=N в итоге думал, что в x^2==a mod N a обязательно должен быть квадратом)

 

--------------------

 

ВОПРОС: Допустим, я могу сократить область поиска факторов в n раз - во сколько уменьшится матрица gnfs??

 

в частных случаях, перебирая 2^t-N можно приближённо найти Y^2.....

 

Для N = P * Q;
f(z) = cos(pi * z) * cos(pi * N / z) - 1
Не турдно догадатся что множители N - корни f(z).

Пусть g(z) = z*f'(z)/f(z),
U(delta) = int(x=1+0.5 .. n-0.5, g(x+i*delta))
то
P+Q = lim(delta->0, U(delta)-U(-delta))

хехе..

П.С.
int(z=a..b,f(z)) - интеграл для f(z) с пределами от a до b
lim(z->0, f(z)) предел f(z) при z->0
pi = 3.14...
i = мнимая единица

П.П.С. Я не питаю никаких иллюзий на счет этой задачи

 

blood

не совсем понял-ты хочешь изречь, что это нормальное быстрое нахождение факторов???

 

Я хотел сказать, что написаное мной не более чем любопытно

 

blood

это производная??

 

blood
значит ты один из тех, кто думает, что рса не потопляемый)

 

blood

Что-то не так с пределами интегрирования, получается, что U зависит от неизвестного параметра n.

 

crypto
вообще, мне в формуле не ясно откуда взяты пределы интегрирования.

 

Точно.

n - это N=P*Q. Очень даже известный параметр

Пределы должны содержать в своем промежутке P и Q. Для того, чтобы исключить из суммы делители 1 и N прибавил и вычел 0.5

 

к тому же при f(z)=0, g(z) неопределена в точки z: по идее, чтобы установить приделы интегр. не затрагивающие точку разрыва нужно знать факторы.

 

при достаточно малом delta>0, f(z) всегда(на промежутке интегрирования) не 0

Немножко ошибся: предел надо еще на 4*pi*i поделить..

 

blood

мда... спасибо повесилил) - такой подход на подсосе у товарища брута, короче, фффффффтопку маздая... едем дальше))

 

blood

Мы же не на Паскале изъясняемся

 

можно раскладывать так:
N mod Z== (p mod Z)*(q mod Z)==(p mod Z)*(q mod Z) mod Z==r
тогда разложив r можно получит q mod Z=k, и тогда t*Z+k=q (Z~N^.5/10)
P. S.
так можно расскатать 1024 бит, если сильно повезёт с остатком)
P.P.S.
если захотите реализовать енту методу - рекомендую внедрить возможность ручного выбора Z: это позволит сделать более хороший сплав вашего шестого чувства и автомата......)