Факторизация

Сообщение №6370 от Побережный Александр 13 января 2003 г. 15:20
Тема: Факторизация

Уважаемые участники форума! Хочу привлечь Ваше внимание к проблеме факторизации натуральных чисел (разложение на множители).
Пусть N - некоторое натуральное число.
Функция ((k^2+N)^0.5)-k выдает множители числа N при целочисленном решении функции, где k-0,1,2,3,...
Мне кажется это довольно быстрый способ разложения чисел.


Отклики на это сообщение:

Ты это сам придумал?
Очень интересно узнать:
- сколько тебе лет?
- где ты учишься?


> Ты это сам придумал?
> Очень интересно узнать:
> - сколько тебе лет?
> - где ты учишься?

Мне 36 лет.
Закончил МИФИ. Работаю в Роэнергоатоме.
А как это относиться к теме? :)


> Уважаемые участники форума! Хочу привлечь Ваше внимание к проблеме факторизации натуральных чисел (разложение на множители).
> Пусть N - некоторое натуральное число.
> Функция ((k^2+N)^0.5)-k выдает множители числа N при целочисленном решении функции, где k-0,1,2,3,...
> Мне кажется это довольно быстрый способ разложения чисел.

Например, для N=3 ну никак не работает формула
((k^2+9)^0.5)-k =3
(k^2+9)=(k+3)^2
0<>6k ексли k<>0


> > Уважаемые участники форума! Хочу привлечь Ваше внимание к проблеме факторизации натуральных чисел (разложение на множители).
> > Пусть N - некоторое натуральное число.
> > Функция ((k^2+N)^0.5)-k выдает множители числа N при целочисленном решении функции, где k-0,1,2,3,...
> > Мне кажется это довольно быстрый способ разложения чисел.

> Например, для N=3 ну никак не работает формула
> ((k^2+9)^0.5)-k =3
> (k^2+9)=(k+3)^2
> 0<>6k ексли k<>0

У вас ошибка. Если N=3, то почему в формуле 9? В формуле и должно быть 3.


> > > Уважаемые участники форума! Хочу привлечь Ваше внимание к проблеме факторизации натуральных чисел (разложение на множители).
> > > Пусть N - некоторое натуральное число.
> > > Функция ((k^2+N)^0.5)-k выдает множители числа N при целочисленном решении функции, где k-0,1,2,3,...
> > > Мне кажется это довольно быстрый способ разложения чисел.

> > Например, для N=3 ну никак не работает формула
> > ((k^2+9)^0.5)-k =3
> > (k^2+9)=(k+3)^2
Я имел в виду N=9
> > 0<>6k ексли k<>0

> У вас ошибка. Если N=3, то почему в формуле 9? В формуле и должно быть 3.


> > > > Уважаемые участники форума! Хочу привлечь Ваше внимание к проблеме факторизации натуральных чисел (разложение на множители).
> > > > Пусть N - некоторое натуральное число.
> > > > Функция ((k^2+N)^0.5)-k выдает множители числа N при целочисленном решении функции, где k-0,1,2,3,...
> > > > Мне кажется это довольно быстрый способ разложения чисел.

> > > Например, для N=3 ну никак не работает формула
> > > ((k^2+9)^0.5)-k =3
> > > (k^2+9)=(k+3)^2
> > > 0<>6k ексли k<>0

> > У вас ошибка. Если N=3, то почему в формуле 9? В формуле и должно быть 3.

Я имел в виду N=9


> > > > Уважаемые участники форума! Хочу привлечь Ваше внимание к проблеме факторизации натуральных чисел (разложение на множители).
> > > > Пусть N - некоторое натуральное число.
> > > > Функция ((k^2+N)^0.5)-k выдает множители числа N при целочисленном решении функции, где k-0,1,2,3,...
> > > > Мне кажется это довольно быстрый способ разложения чисел.

> > > Например, для N=3 ну никак не работает формула
> > > ((k^2+9)^0.5)-k =3
> > > (k^2+9)=(k+3)^2
> Я имел в виду N=9
> > > 0<>6k ексли k<>0

> > У вас ошибка. Если N=3, то почему в формуле 9? В формуле и должно быть 3.

При к=0 уравнение дает верный результат.


> > > > > Уважаемые участники форума! Хочу привлечь Ваше внимание к проблеме факторизации натуральных чисел (разложение на множители).
> > > > > Пусть N - некоторое натуральное число.
> > > > > Функция ((k^2+N)^0.5)-k выдает множители числа N при целочисленном решении функции, где k-0,1,2,3,...
> > > > > Мне кажется это довольно быстрый способ разложения чисел.

> > > > Например, для N=3 ну никак не работает формула
> > > > ((k^2+9)^0.5)-k =3
> > > > (k^2+9)=(k+3)^2
> > Я имел в виду N=9
> > > > 0<>6k ексли k<>0

> > > У вас ошибка. Если N=3, то почему в формуле 9? В формуле и должно быть 3.

> При к=0 уравнение дает верный результат.

Да действительно - не продумал о таком тривиальном варианте
насколько я понимаю ноги растут из следующего
Пусть наше число составное N=a*b
Тогда Ваше соотношение означает
k^2+a*b=(a+k)^2 (или k^2+a*b=(b+k)^2 - из соотношений симметрии не важно)
или
a*b=a^2+2*a*k
Сократим на а<>0
b=a+2*k
b-a=2*k
если b и а одинаковой четности - то все буде O'key
Но для N=6, например, будут проблемы



> Да действительно - не продумал о таком тривиальном варианте
> насколько я понимаю ноги растут из следующего
> Пусть наше число составное N=a*b
> Тогда Ваше соотношение означает
> k^2+a*b=(a+k)^2 (или k^2+a*b=(b+k)^2 - из соотношений симметрии не важно)
> или
> a*b=a^2+2*a*k
> Сократим на а<>0
> b=a+2*k
> b-a=2*k
> если b и а одинаковой четности - то все буде O'key
> Но для N=6, например, будут проблемы


Если a и b - разной чётности, то надо применять следующую формулу:

А идея мне нравится!


>
> > Да действительно - не продумал о таком тривиальном варианте
> > насколько я понимаю ноги растут из следующего
> > Пусть наше число составное N=a*b
> > Тогда Ваше соотношение означает
> > k^2+a*b=(a+k)^2 (или k^2+a*b=(b+k)^2 - из соотношений симметрии не важно)
> > или
> > a*b=a^2+2*a*k
> > Сократим на а<>0
> > b=a+2*k
> > b-a=2*k
> > если b и а одинаковой четности - то все буде O'key
> > Но для N=6, например, будут проблемы

>
> Если a и b - разной чётности, то надо применять следующую формулу:

>

> А идея мне нравится!


>
> > Да действительно - не продумал о таком тривиальном варианте
> > насколько я понимаю ноги растут из следующего
> > Пусть наше число составное N=a*b
> > Тогда Ваше соотношение означает
> > k^2+a*b=(a+k)^2 (или k^2+a*b=(b+k)^2 - из соотношений симметрии не важно)
> > или
> > a*b=a^2+2*a*k
> > Сократим на а<>0
> > b=a+2*k
> > b-a=2*k
> > если b и а одинаковой четности - то все буде O'key
> > Но для N=6, например, будут проблемы

>
> Если a и b - разной чётности, то надо применять следующую формулу:

>

> А идея мне нравится!

Можно предложить еще более крутую идею (и более эффективную кстати)

a = N/k


Вот, кстати, общая формула, работающая при любой чётности a и b:

В общем случае Ваш алгоритм факторизации гораздо менее эффективен, чем метод простого деления. Но если b-a мало, то Ваш способ очень эффективен. К тому же, вероятно, есть возможность его усовершенствовать.

Хочу Вас спросить. Вы знаете какой-нибудь язык программирования? Если да, то какой?


> Вот, кстати, общая формула, работающая при любой чётности a и b:

>

> В общем случае Ваш алгоритм факторизации гораздо менее эффективен, чем метод простого деления. Но если b-a мало, то Ваш способ очень эффективен. К тому же, вероятно, есть возможность его усовершенствовать.

> Хочу Вас спросить. Вы знаете какой-нибудь язык программирования? Если да, то какой?

Посмотрите, например в
Нил Коблиц
Курс теории чисел и криптографии

Глава V. Простота и факторизация
5.1 Псевдопростые числа
5.2 Ро-метод
5.3 Факторизция Ферма и факторные базы
5.4 Метод цепных дробей
5.5 Метод квадратичного решета

http://www.tvp.ru/ourizd/ourizdfr.htm

метод Ферма в различных модификациях.

Пока я не увидел каких-то идейных отличий.


> Вот, кстати, общая формула, работающая при любой чётности a и b:

>

> В общем случае Ваш алгоритм факторизации гораздо менее эффективен, чем метод простого деления. Но если b-a мало, то Ваш способ очень эффективен. К тому же, вероятно, есть возможность его усовершенствовать.

> Хочу Вас спросить. Вы знаете какой-нибудь язык программирования? Если да, то какой?

Я ушел от четности, чтобы исчезли лишние коэфициенты в формуле и формула проще смотрелась. Алгоритм можно и усовершенствовать, например избавиться от радикала.
Увы, я не профессиональный программист. Просто пользователь.


> > Вот, кстати, общая формула, работающая при любой чётности a и b:

> >

> > В общем случае Ваш алгоритм факторизации гораздо менее эффективен, чем метод простого деления. Но если b-a мало, то Ваш способ очень эффективен. К тому же, вероятно, есть возможность его усовершенствовать.

> > Хочу Вас спросить. Вы знаете какой-нибудь язык программирования? Если да, то какой?

> Посмотрите, например в
> Нил Коблиц
> Курс теории чисел и криптографии

> Глава V. Простота и факторизация
> 5.1 Псевдопростые числа
> 5.2 Ро-метод
> 5.3 Факторизция Ферма и факторные базы
> 5.4 Метод цепных дробей
> 5.5 Метод квадратичного решета

> http://www.tvp.ru/ourizd/ourizdfr.htm

> метод Ферма в различных модификациях.

> Пока я не увидел каких-то идейных отличий.

Михалыч, а что общего можно указать с методом Ферма?


Уважаемый Александр,
проблема которую вы рассматриваете была подана на регистрацию нами 8 октября и запатентована 5 декабря 2002 года. Проблема решена в программном обеспечении на языке С++. До этого мы уже давно использовали подход при решении своих частных задач.


> Уважаемый Александр,
> проблема которую вы рассматриваете была подана на регистрацию нами 8 октября и запатентована 5 декабря 2002 года. Проблема решена в программном обеспечении на языке С++. До этого мы уже давно использовали подход при решении своих частных задач.


А вы не могли бы поделиться исходниками Вашей программы? Был бы Вам очень признателен.

Мой e-mail: letterto@mail.ru


Просто смешно!!!!!!!!!!!

Эта формула есть метод Ферма факторизации чисел:))) см. линк ниже
Прошло много лет и вот додумались и даже патент получили

http://www.cryptography.ru/db/msg.html?mid=1161235&uri=node35.html

http://www.cryptography.ru/db/msg.html?mid=1161235&uri=node35.html


> Уважаемый Александр,
> проблема которую вы рассматриваете была подана на регистрацию нами 8 октября и запатентована 5 декабря 2002 года. Проблема решена в программном обеспечении на языке С++. До этого мы уже давно использовали подход при решении своих частных задач.

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


факторизация

Сообщение от Anka , 06 февраля 2003 г. 03:54:

Народ, существует ли какой-нибудь алгоритм факторизации матрицы в произведение двух ВЕРХНИХ треугольных матриц (да еще и с нулевой диагональю)????


Физика в анимациях - Купить диск - Тесты по физике - Графики on-line

Реклама:
Rambler's Top100