Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 2 3 [4] 5   вперед  Ctrl      все
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
Изучаю китайскую ттеорему об остатках. Нашел:
http://vuz.exponenta.ru/PDF/book/ChinaT.html
посмотрел на поиск yi...

mayton,

поиск yi ничего не напоминает?
13 мар 20, 11:42    [22098283]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
mayton
Member

Откуда: loopback
Сообщений: 47948
Нет ничего не напоминает. Я давно уже не слежу за твоими числовыми исследованиями.
Мне они пока неинтересны. Я целиком в графовых задачах и в изучении ФП.
13 мар 20, 12:04    [22098320]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Имя пользователя1
Member

Откуда:
Сообщений: 654
mayton
Я целиком в графовых задачах
если что интересное и небанальное встретится, выкладывай на форум )
13 мар 20, 12:24    [22098357]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
mayton
Нет ничего не напоминает. Я давно уже не слежу за твоими числовыми исследованиями.
Мне они пока неинтересны. Я целиком в графовых задачах и в изучении ФП.
А это расстановка ферзей на доске с одинаковым шагом.

Поворачиваем доску на 90 градусов и находим решение с одного шага.
13 мар 20, 12:28    [22098366]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
mayton
Member

Откуда: loopback
Сообщений: 47948
Gennadiy Usov
mayton
Нет ничего не напоминает. Я давно уже не слежу за твоими числовыми исследованиями.
Мне они пока неинтересны. Я целиком в графовых задачах и в изучении ФП.
А это расстановка ферзей на доске с одинаковым шагом.

Поворачиваем доску на 90 градусов и находим решение с одного шага.

Я-бы был рад в это поверить если не другой факт. Этой задачей занимались много лет
и никто не доказал существование полиномиального решения для остаточной расстановки.

Зачем мы тревожим труп? Пускай себе лежит.
13 мар 20, 13:15    [22098412]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
mayton,

ты столько потревожил ...., этих, на форуме "Программирование", что одним больше, одним меньше...
13 мар 20, 14:57    [22098537]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
mayton
Member

Откуда: loopback
Сообщений: 47948
Вот я раскаялся в этих действиях и ушел в Тибет читать молитвы
графы решать графовые задачи на ФП.
13 мар 20, 15:21    [22098568]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Barlone
Member

Откуда:
Сообщений: 1401
Gennadiy Usov
Изучаю китайскую ттеорему об остатках. Нашел:
http://vuz.exponenta.ru/PDF/book/ChinaT.html

Найти решение системы сравнений
x=2(mod 5),
x=15(mod 17),
x=5(mod 12).

import math


def invmod(a, b):
  if b == 0:
    return 0
  x2 = 1
  x1 = 0
  y2 = 0
  y1 = 1
  d = b
  while b > 0:
    q = a // b
    r = a - q * b
    x = x2 - q * x1
    y = y2 - q * y1
    a = b
    b = r
    x2 = x1
    x1 = x
    y2 = y1
    y1 = y
  if a == 1:
    if x2 > 0:
      return x2
    else:
      return d + x2
  else:
    return 0

def chinese_rems(mods):
    mod_mults = []
    p_mods = 1
    
    def rem_restore(rems):
        nonlocal mod_mults, p_mods 
        sm = 0
        for i in range(len(rems)):
            sm += rems[i] * mod_mults[i] % p_mods
        return sm % p_mods

    for i in mods:
        p_mods *= i
    for i in mods:
        mod_mults.append(invmod(p_mods//i, i) * (p_mods//i) % p_mods)
    return rem_restore

f = chinese_rems([5,17,12])
print (f([2,15,5]))
14 мар 20, 07:01    [22098965]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
Barlone,

спасибо за программу!

А при прогоне идут ошибки компиляции...

Сообщение было отредактировано: 14 мар 20, 07:26
14 мар 20, 07:23    [22098966]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Barlone
Member

Откуда:
Сообщений: 1401
Gennadiy Usov

А при прогоне идут ошибки компиляции...
Старая версия питона?
14 мар 20, 07:38    [22098968]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
Traceback (most recent call last):
File "<string>", line 1, in <module>
File "/usr/lib/python2.7/py_compile.py", line 117, in compile
raise py_exc
py_compile.PyCompileError: File "prog.py", line 36
nonlocal mod_mults, p_mods
^
SyntaxError: invalid syntax


При копировании прошла сдвижка влево на 6 позиций. Стрелка под s.

А в Python 3.7.4 прошло!
797
>>>

Сообщение было отредактировано: 14 мар 20, 07:46
14 мар 20, 07:44    [22098969]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
Получилась интересная ситуация с китайской теоремой.

С первого раза находится число,
если оно меньше произведения всех модулей.

Далее надо прибавлять это произведение модулей до нахождения нужного.

Сообщение было отредактировано: 15 мар 20, 07:39
15 мар 20, 07:30    [22099251]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
kealon(Ruslan)
Member

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

Гугли "система остаточных классов"
15 мар 20, 21:43    [22099531]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
Кстати, а какое соотношение между площадью и периметром прямоугольника?
8 май 20, 07:58    [22129129]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Dima T
Member

Откуда:
Сообщений: 14878
Gennadiy Usov
Кстати, а какое соотношение между площадью и периметром прямоугольника?

Никакого
8 май 20, 08:05    [22129132]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6013
Gennadiy Usov
Кстати, а какое соотношение между площадью и периметром прямоугольника?
ab/[2(a + b)]
8 май 20, 09:00    [22129142]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
mayton
Member

Откуда: loopback
Сообщений: 47948
Если z = f(x,y) = x * y/[2(x + y)]

то это поверхность близкая к плоскости, и вдоль прямой x = y эта поверхность рвётся
и улетает либо в минус бесконечность либо в плюс.
8 май 20, 10:23    [22129177]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
Gennadiy Usov
Кстати, а какое соотношение между площадью и периметром прямоугольника?
Почему я задал этот вопрос?

А потому что это отношение похоже на задачу факторизации.

N = A**2 - B**2, N = x*y, A = (x + y)/2
8 май 20, 10:44    [22129189]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
kealon(Ruslan)
Member

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

оно даже больше, чем похоже
fi(p1*p2) = (p1 - 1) (p2 - 1) = p1 * p2 + 1 - (p1 + p2)

но я уже где-то показывал, что размеры нашей вселенной ничто в сравнении цифрами, используемыми даже в текущей криптографии
8 май 20, 21:30    [22129679]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
kealon(Ruslan)
Gennadiy Usov,
оно даже больше, чем похоже
fi(p1*p2) = (p1 - 1) (p2 - 1) = p1 * p2 + 1 - (p1 + p2)
но я уже где-то показывал, что размеры нашей вселенной ничто в сравнении цифрами,
используемыми даже в текущей криптографии
А далее ещё интереснее:

2^N = 2^(x + y - 1) mod(N),
где N = x * y - только два множителя.
10 май 20, 09:03    [22130061]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
kealon(Ruslan)
Member

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

я могу ещё более весомое утверждение дать, в силу отсутствия собственного корня при x<>y

2^[(N + 1)/2] mod N = 2^[(x + y)/2] mod N

только толку от этого мало
12 май 20, 13:50    [22131176]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
kealon(Ruslan)
Gennadiy Usov,
я могу ещё более весомое утверждение дать, в силу отсутствия собственного корня при x<>y
2^[(N + 1)/2] mod N = 2^[(x + y)/2] mod N
только толку от этого мало
Чем хорошо это уравнение, так это в том, что перебираются не числа от 1 до x + y,
а числа от 1 до (x + y)/2
при переборе 2^.

А если N +1 можно делить ещё раз на 2 (и не один раз), то ещё меньше чисел придётся перебирать.
12 май 20, 14:49    [22131251]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6013
Gennadiy Usov
kealon(Ruslan)
Gennadiy Usov,
я могу ещё более весомое утверждение дать, в силу отсутствия собственного корня при x<>y
2^[(N + 1)/2] mod N = 2^[(x + y)/2] mod N
только толку от этого мало
Чем хорошо это уравнение, так это в том, что перебираются не числа от 1 до x + y,
а числа от 1 до (x + y)/2
при переборе 2^.

А если N +1 можно делить ещё раз на 2 (и не один раз), то ещё меньше чисел придётся перебирать.
неверно
12 май 20, 17:16    [22131402]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
kealon(Ruslan)
Gennadiy Usov
А если N +1 можно делить ещё раз на 2 (и не один раз), то ещё меньше чисел придётся перебирать.
неверно
Почему?
12 май 20, 17:58    [22131435]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
kealon(Ruslan)
Gennadiy Usov
Чем хорошо это уравнение, так это в том, что перебираются не числа от 1 до x + y,
а числа от 1 до (x + y)/2
при переборе 2^.
А если N +1 можно делить ещё раз на 2 (и не один раз), то ещё меньше чисел придётся перебирать.
неверно
Проверил.
Будет верно для (N +1)/4, если (N +1)/8 - чётное.
И так далее.

Сообщение было отредактировано: 12 май 20, 20:28
12 май 20, 20:28    [22131535]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 2 3 [4] 5   вперед  Ctrl      все
Все форумы / Программирование Ответить