Добро пожаловать в форум, Guest >> Войти | Регистрация | Поиск | Правила | | В избранное | Подписаться | ||
Все форумы / Программирование |
![]() ![]() |
Топик располагается на нескольких страницах: ←Ctrl назад 1 .. 23 24 25 26 27 28 29 [30] 31 32 вперед Ctrl→ |
kealon(Ruslan) Member Откуда: Нижневартовск Сообщений: 6228 |
Barlone, перевод части вычислений в СОК, как вариант что-то в этом духе |
25 мар 19, 14:36 [21842827] Ответить | Цитировать Сообщить модератору |
Dimitry Sibiryakov Member Откуда: Сообщений: 52116 |
|
||
25 мар 19, 14:49 [21842845] Ответить | Цитировать Сообщить модератору |
Barlone Member Откуда: Сообщений: 1448 |
kealon(Ruslan), не знаю, метод решета числового поля я не осилил. Но там есть что-то связанное с кольцами... |
25 мар 19, 15:59 [21842924] Ответить | Цитировать Сообщить модератору |
kealon(Ruslan) Member Откуда: Нижневартовск Сообщений: 6228 |
Barlone, Там не то, он простой. Принцип такой же как в квадратичном решете, но немного другим способом гладкость проверяется |
25 мар 19, 16:53 [21842978] Ответить | Цитировать Сообщить модератору |
Barlone Member Откуда: Сообщений: 1448 |
|
||||
26 мар 19, 09:06 [21843406] Ответить | Цитировать Сообщить модератору |
kealon(Ruslan) Member Откуда: Нижневартовск Сообщений: 6228 |
так выходит: возьмём l, такой что l *n | p = 1 т.е. l = n^(-1)|p для дискрентного корня q справедливо (q^2- kn = 1), (q^2 - 1) * l | p = kn * l | p = k для q<n/2, соответственно k < n/4 если q не дискретный корень <n/2, то (q^2 - 1) * l | p >= n/4 |
||||
26 мар 19, 15:53 [21843956] Ответить | Цитировать Сообщить модератору |
Barlone Member Откуда: Сообщений: 1448 |
Пытаемся найти нетривиальный квадратный корень из 1 по модулю n? Тогда gcd(q-1,n) и gcd(q+1,n) даст нам сомножители? |
26 мар 19, 16:30 [21843997] Ответить | Цитировать Сообщить модератору |
Barlone Member Откуда: Сообщений: 1448 |
|
||||
26 мар 19, 16:33 [21844000] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2275 |
Есть уравнение: 4*А^2 - (1+2*B)^2 = P Известно только Р. Не подскажите, как решать это уравнение в целых числах? Если перебирать А и В, то это очень много времени... |
26 мар 19, 17:00 [21844035] Ответить | Цитировать Сообщить модератору |
kealon(Ruslan) Member Откуда: Нижневартовск Сообщений: 6228 |
т.ч. (q^2 - 1) * l | p < n/4 для дискретного корня <n/2 верно всегда |
||||
26 мар 19, 17:01 [21844037] Ответить | Цитировать Сообщить модератору |
kealon(Ruslan) Member Откуда: Нижневартовск Сообщений: 6228 |
замени 2 A = x , 1+2*B = y x^2 - y^2 = (x -y) * (x + y) = P разложи P на множители, дальше строишь системы с их комбинациями |
||
26 мар 19, 17:10 [21844048] Ответить | Цитировать Сообщить модератору |
Barlone Member Откуда: Сообщений: 1448 |
|
||
26 мар 19, 17:54 [21844122] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2275 |
То есть, Р равно только 1, 3, 7, 9. |
||||
26 мар 19, 18:15 [21844145] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2275 |
Если Р очень и очень большое, то таких вычислений будет около Р^2. Если не будет каких-нибудь ограничений. |
||||
26 мар 19, 18:35 [21844159] Ответить | Цитировать Сообщить модератору |
kealon(Ruslan) Member Откуда: Нижневартовск Сообщений: 6228 |
Gennadiy Usov, Если Р очень и очень большое, то зашибёшся его факторизовывать, а само решение фигня будет |
26 мар 19, 19:05 [21844181] Ответить | Цитировать Сообщить модератору |
mayton Member Откуда: loopback Сообщений: 50489 |
Gennadiy Usov, бегай по "четвертушке" эллипса. |
26 мар 19, 19:11 [21844183] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2275 |
а жалко... |
||
26 мар 19, 19:12 [21844186] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2275 |
А если серьёзно, то всё равно перебор, хоть по эллипсу, хоть... |
||
26 мар 19, 19:14 [21844189] Ответить | Цитировать Сообщить модератору |
Barlone Member Откуда: Сообщений: 1448 |
Представление в виде разности квадратов - один из методов факторизации |
26 мар 19, 19:41 [21844217] Ответить | Цитировать Сообщить модератору |
Barlone Member Откуда: Сообщений: 1448 |
Но если надо одно решение, то P = (P+1)2/4 - (P-1)2/4 |
26 мар 19, 19:45 [21844222] Ответить | Цитировать Сообщить модератору |
mayton Member Откуда: loopback Сообщений: 50489 |
Да. Перебор. А ты как хотел? |
||||
26 мар 19, 19:51 [21844228] Ответить | Цитировать Сообщить модератору |
kealon(Ruslan) Member Откуда: Нижневартовск Сообщений: 6228 |
Barlone, алгоритм Полларда как раз использует СОК |
27 мар 19, 11:58 [21844829] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2275 |
Кстати, может быть множество решений: P = (P+n)2/4/n - (P-n)2/4/n, где n<P |
||
27 мар 19, 15:56 [21845214] Ответить | Цитировать Сообщить модератору |
Barlone Member Откуда: Сообщений: 1448 |
|
||||
27 мар 19, 16:03 [21845224] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2275 |
|
||||
27 мар 19, 16:26 [21845242] Ответить | Цитировать Сообщить модератору |
Топик располагается на нескольких страницах: ←Ctrl назад 1 .. 23 24 25 26 27 28 29 [30] 31 32 вперед Ctrl→ |
Все форумы / Программирование | ![]() |