Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: ←Ctrl  назад   1 .. 23 24 25 26 27 28 29 [30] 31 32   вперед  Ctrl→
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6228
 		Barlone,

перевод части вычислений в СОК, как вариант

что-то в этом духе
25 мар 19, 14:36    [21842827]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 52116
Dima T
Эта задача легко решается: перемножай простые пока не получишь составное нужного размера.
Она решается ещё проще: генерируется нужное количество бит, потом последний обнуляется.
25 мар 19, 14:49    [21842845]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Barlone
Member

Откуда:
Сообщений: 1448
 		kealon(Ruslan), не знаю, метод решета числового поля я не осилил. Но там есть что-то связанное с кольцами...
25 мар 19, 15:59    [21842924]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6228
 		Barlone,

Там не то, он простой. Принцип такой же как в квадратичном решете, но немного другим способом гладкость проверяется
25 мар 19, 16:53    [21842978]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Barlone
Member

Откуда:
Сообщений: 1448
kealon(Ruslan)
Barlone
пропущено...
Эллиптические кривые?
всё таки не то
я имею ввиду со сменой кольца вычетов
например, разложение n=a*b, а вот взять другое полностью нам известное кольцо и как-то привести задачу к нему

пусть возьмём простое p > n*n/2

q>1 удовлетворяющее [n^(-1)|p] * [q^2 - 1] < n/4. будет дискретным корнем
Что-то я эту формулу не понял
26 мар 19, 09:06    [21843406]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6228
Barlone
kealon(Ruslan)
пропущено...
всё таки не то
я имею ввиду со сменой кольца вычетов
например, разложение n=a*b, а вот взять другое полностью нам известное кольцо и как-то привести задачу к нему

пусть возьмём простое p > n*n/2

q>1 удовлетворяющее [n^(-1)|p] * [q^2 - 1] < n/4. будет дискретным корнем
Что-то я эту формулу не понял

так выходит:
возьмём 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]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Barlone
Member

Откуда:
Сообщений: 1448
 		Пытаемся найти нетривиальный квадратный корень из 1 по модулю n? Тогда gcd(q-1,n) и gcd(q+1,n) даст нам сомножители?
26 мар 19, 16:30    [21843997]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Barlone
Member

Откуда:
Сообщений: 1448
kealon(Ruslan)
Barlone
пропущено...
Что-то я эту формулу не понял

так выходит:
возьмём 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
Так не получается, если мы проведем вычисления по модулю p, то вместо q^2- kn = 1 получим q^2- kn = 1 + x*p
26 мар 19, 16:33    [21844000]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2275
 		Есть уравнение:

4*А^2 - (1+2*B)^2 = P

Известно только Р.

Не подскажите,
как решать это уравнение в целых числах?

Если перебирать А и В, то это очень много времени...
26 мар 19, 17:00    [21844035]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6228
Barlone
Пытаемся найти нетривиальный квадратный корень из 1 по модулю n? Тогда gcd(q-1,n) и gcd(q+1,n) даст нам сомножители?
задача равноценная, просто к чему легче всего зацепиться на вскидку

Barlone
вместо q^2- kn = 1 получим q^2- kn = 1 + x*p
не получим, мы ж ЗНАЕМ задали что q^2 < p

т.ч. (q^2 - 1) * l | p < n/4 для дискретного корня <n/2 верно всегда
26 мар 19, 17:01    [21844037]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6228
Gennadiy Usov
Есть уравнение:

4*А^2 - (1+2*B)^2 = P

Известно только Р.

Не подскажите,
как решать это уравнение в целых числах?

Если перебирать А и В, то это очень много времени...

замени 2 A = x , 1+2*B = y

x^2 - y^2 = (x -y) * (x + y) = P
разложи P на множители, дальше строишь системы с их комбинациями
26 мар 19, 17:10    [21844048]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Barlone
Member

Откуда:
Сообщений: 1448
Gennadiy Usov
Есть уравнение:

4*А^2 - (1+2*B)^2 = P

Известно только Р.

Не подскажите,
как решать это уравнение в целых числах?

Если перебирать А и В, то это очень много времени...
Если к примеру p % 4 != 3, то решений вообще нет.
26 мар 19, 17:54    [21844122]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2275
Barlone
Gennadiy Usov
Есть уравнение:
4*А^2 - (1+2*B)^2 = P
Известно только Р.
Не подскажите,как решать это уравнение в целых числах?
Если перебирать А и В, то это очень много времени...
Если к примеру p % 4 != 3, то решений вообще нет.
Добавление: Р не является чётным числом, и не равно 5.
То есть, Р равно только 1, 3, 7, 9.
26 мар 19, 18:15    [21844145]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2275
kealon(Ruslan)
Gennadiy Usov
Есть уравнение:
4*А^2 - (1+2*B)^2 = P
Известно только Р.
Не подскажите,как решать это уравнение в целых числах?
Если перебирать А и В, то это очень много времени...
замени 2 A = x , 1+2*B = y
x^2 - y^2 = (x -y) * (x + y) = P
разложи P на множители, дальше строишь системы с их комбинациями
То есть, кроме простого перебора А и В или х и y, ничего не получится?

Если Р очень и очень большое, то таких вычислений будет около Р^2.
Если не будет каких-нибудь ограничений.
26 мар 19, 18:35    [21844159]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6228
 		Gennadiy Usov,

Если Р очень и очень большое, то зашибёшся его факторизовывать, а само решение фигня будет
26 мар 19, 19:05    [21844181]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
mayton
Member

Откуда: loopback
Сообщений: 50489
 		Gennadiy Usov, бегай по "четвертушке" эллипса.
26 мар 19, 19:11    [21844183]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2275
kealon(Ruslan)
Gennadiy Usov,
Если Р очень и очень большое, то зашибёшся его факторизовывать, а само решение фигня будет
Я тоже так думаю,
а жалко...
26 мар 19, 19:12    [21844186]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2275
mayton
Gennadiy Usov, бегай по "четвертушке" эллипса.
В какую сторону?

А если серьёзно, то всё равно перебор, хоть по эллипсу, хоть...
26 мар 19, 19:14    [21844189]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Barlone
Member

Откуда:
Сообщений: 1448
 		Представление в виде разности квадратов - один из методов факторизации
26 мар 19, 19:41    [21844217]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Barlone
Member

Откуда:
Сообщений: 1448
 		Но если надо одно решение, то P = (P+1)2/4 - (P-1)2/4
26 мар 19, 19:45    [21844222]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
mayton
Member

Откуда: loopback
Сообщений: 50489
Gennadiy Usov
mayton
Gennadiy Usov, бегай по "четвертушке" эллипса.
В какую сторону?

А если серьёзно, то всё равно перебор, хоть по эллипсу, хоть...

Да. Перебор. А ты как хотел?
26 мар 19, 19:51    [21844228]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6228
 		Barlone,

алгоритм Полларда как раз использует СОК
27 мар 19, 11:58    [21844829]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2275
Barlone
Но если надо одно решение, то P = (P+1)2/4 - (P-1)2/4
Спасибо за формулу!

Кстати, может быть множество решений:
P = (P+n)2/4/n - (P-n)2/4/n, где n<P
27 мар 19, 15:56    [21845214]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Barlone
Member

Откуда:
Сообщений: 1448
Gennadiy Usov
Barlone
Но если надо одно решение, то P = (P+1)2/4 - (P-1)2/4
Спасибо за формулу!

Кстати, может быть множество решений:
P = (P+n)2/4/n - (P-n)2/4/n, где n<P
А если n не квадрат? А если P не делится на n?
27 мар 19, 16:03    [21845224]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2275
Barlone
Gennadiy Usov
пропущено...
Спасибо за формулу!
Кстати, может быть множество решений:
P = (P+n)2/4/n - (P-n)2/4/n, где n<P
А если n не квадрат? А если P не делится на n?
Так это тождество!
27 мар 19, 16:26    [21845242]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: ←Ctrl  назад   1 .. 23 24 25 26 27 28 29 [30] 31 32   вперед  Ctrl→
Все форумы / Программирование Ответить