2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу Пред.  1, 2, 3
 
 
Сообщение06.06.2007, 20:14 
Аватара пользователя
Именно в контексте данной темы :)

 
 
 
 
Сообщение07.07.2007, 09:34 
p-h-o-e-n-i-x писал(а):
Именно в контексте данной темы :)


Определение, вытекающее из решета Эратосфена :) и инерпретации p-h-o-e-n-i-x'а :

"Любое целое число, взаимнопростое с примориалом $  \prod\limits_{i=2}^{p_k} $, непревышающее
$ {p_k}^2 $, является простым".

 
 
 
 
Сообщение22.09.2007, 14:31 
Вроде, немного разобрался с методами факторизации: по Ферма и при помощи треугольных чисел.
Оказывается, что это "звенья одной цепи", а именно:
Проверка методом Ферма осуществляется путем проверки:
$ N = a^2 - b^2 $, откуда $ N = pq = (a - b)(a +b) $, $ p = a - b $, $ q = a + b $,

а проверка методом треугольных чисел - путем проверки выражений:
$ N = \frac{a(a + 1)}{2} - \frac{b(b + 1)}{2} $ или $ N = pq = \frac{(a - b)(a + b + 1)}{2} $, откуда получаем два варианта:
- либо $ p = \frac{(a - b)}{2} $, $ q = a + b + 1 $,
- либо $ p = a - b $, $ q = \frac{(a + b + 1)}{2} $.

Эти два метода можно объединить в один:
$ N = a(a + k) - b(b + k) $, где $ k $ - целое число, или $ N = pq = (a - b)(a + b + k) $, где
$ p = (a - b) $, $ q = a + b + k $.
Для метода Ферма $ k = 0 $,
для метода треугольных чисел $ k = 1 $ (для "экономии" получаемые четные числа (при любых k нечетных) делятся на 2).

Но ведь можно пойти по пути дальнейшего изменения $ k $, при каждом из которых проводить по одному раунду (пока не дойдем до того k, которое соответствует соотношению делителей числа N).

 
 
 
 
Сообщение26.11.2007, 21:38 
Аватара пользователя
Вот, кстати, интересная статья

 
 
 
 
Сообщение26.12.2007, 11:05 
Хочу предложить еще один способ факторизации чисел.
Алгоритм его реализации следующий:

Дано число $ N = ab $ $ a < b $.
Выбираем квадрат числа, превышающий $ N $, например, $ C^2 $.
Определяем остаток $ C^2\equiv c (mod N) $
Далее:
1. Проверяем не является ли полученный остаток квадратом какого-либо числа. Если – да, то проводим факторизацию аналогично методу Ферма. Если – нет, переходим к следующему пункту.
2. Проверяем, не имеют ли $ c, N $ общих делителей. Если – нет, то переходим к следующему пункту.
3. Производим последовательную проверку на наличие общих делителей у чисел $ N $ и $ [(D+i)^2-c] $, где $ i = 0, 1, 2, 3,… $, а $ D^2 $ - ближайший квадрат числа, превосходящий $ c $.

Естественно, что для реализации данного способа потребуется промежуточная факторизация большого количества чисел, но на мой взгляд, общая трудоемкость может быть меньше, чем у способов факторизации с применением решета Эратосфена и метода Ферма.
Преимущество заключается в следующем:
1.Если отношение $ \frac{b}{a} $ близко к единице, то должна получиться факторизация по Ферма (п. 1).
2.Если отношение $ \frac{b}{a} $ отлично от упомянутого, то количество проверяемых чисел меняется периодически от $ 1 $ до $ (a-1) $, т.е. в любом случае не превосходит количество чисел, проверяемых решетом Эратосфена. Эта периодичность зависит от того, какое число $ C^2 $ выбрал дешифровальщик для проверки, поэтому бОльшая или меньшая трудоемкость не может быть заранее запрограммирована шифровальщиком.

 
 
 
 Re: Сколько существует определений простых чисел?
Сообщение11.03.2010, 03:00 
Аватара пользователя
Вот я когда-то занимался прайм числами в комплексной области.
Потом на форуме кто-то сказал, что это вроде числа Галуа.
К примеру, 5 уже не простое, поскольку сумма двух квадратов.
Дальше перейти в кватернионы поленился.
А вообще надо заниматься теорией непрерывных квазигрупп.
Там много интересного для математика и физиков тем более.

 
 
 
 Re: Сколько существует определений простых чисел?
Сообщение05.09.2010, 12:11 
Батороев в сообщении #62782 писал(а):
Какие определения простых чисел существуют (или могли быть сформулированы на основании существующих знаний) в теории чисел?

Назову определения, которые мне известны:
1. Простое число p – это то число, которое делится только на 1 или на само себя.
2. Простое число p – это нечетное натуральное число, не являющееся квадратом другого числа, и которое можно выразить в виде разности квадратов чисел не более, чем единственным способом, а именно:
$ p = [\frac{(p+1)}{2}]^2  -  [\frac{(p-1)}{2}]^2 $.
Исключение – простое число 2.
3. Простое число p – это число, которое удовлетворяет условию сравнения:
$ a^{p-1}\equiv{1(mod p)}$,
где a – любое целое число, не превосходящее p.

Определение - вещь весьма и весьма субъективная. Скажем, я могу определить простое число, как натуральное число, в восьмеричной записи которого имеется не более пяти различных цифр. Другое дело, что моё определение диссонирует с конвенциональными (общепринятыми) определениями (и, заметьте, противоречит им). Но данное обстоятельство не лишает меня права на собственное определение простого числа :-) .
Любая математическая теория строится на определениях, аксиомах и правилах вывода. И те, и другие, и третьи могут задаваться произвольно (по желанию автора теории). Помните анекдот, в котором звучит фраза "определим пустой дом, как дом, в котором не более одного человека"? Если не помните (или (быть может) не знаете), попытайтесь найти в Сети.
Удачи Вам!

 
 
 
 Re: Сколько существует определений простых чисел?
Сообщение09.12.2010, 19:54 
Аватара пользователя
Вот тут непонятно, относится этот вопрос к комбинаторике(сколько) или к теории чисел.
Возможно, опять повторяюсь, но сначала надо определить, с чем имеем дело.
Обычно имеется в виду натуральные - целые положительные.
Далее можно обобщить до целых комплексных(там отпадают которые сумма квадратов), кватернионов и октав.
С другой стороны, подозреваю, что-то подобное в числах Галуа и далее перейти на группы, забыл как там простые называются, но это уже классификация и далеко не арифметика.

 
 
 [ Сообщений: 38 ]  На страницу Пред.  1, 2, 3


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group