суббота, 21 июля 2018 г.

факторизация: теория к Ферма и + новый. к Мысли2


моя теория к методу факторизации Ферма. 
плюс еще один метод факторизации.

Любое произвольное число можно выразить в виде:
z = x * y                                                                                                                     (1)
Принимаю: x, y, z – натуральные числа, x ≥ y, x ≠ 0, y ≠ 0, отсюда x ϵ ( ( √z ) ; z ), y ϵ ( 1 ; ( √z ) ), кроме этого, дополнительно ограничиваю, что z – не четное, не кратное 5, так как искать минимальный простой множитель для чётных, или заканчивающихся на 5 или 0, математически скучно, следовательно и множители x и y тоже нечетные. Также принимаю, что z не имеет целого корня квадратного. В таких условиях задача разложения числа z на множители сводится к поиску минимального простого числа, являющегося младшим множителем y > 1 методом перебора по формуле:
            x = z / y                                                                                                                    (2)
Так как количество простых чисел, например, менее 1 миллиона, составляет 78498 штук, то есть 7,85%, и с возрастанием значения чисел процентное содержание простых чисел уменьшается, а максимальное возможное значение меньшего простого множителя y = ( √z ), то теоретическая максимальная вычислительная сложность задачи поиска меньшего простого множителя в худшем случае составляет (0,08√z) раз выполнить деление по формуле2, с последовательным перебором в качестве делителя y простых чисел в диапазоне от 3 до √z включительно. Следует учесть, что деление не является вычислительно простым действием, а состоит из последовательного вычитания, и с увеличением значения y, количество базовых действий  для выполнения следующего деления увеличивается.
В общем случае принятых ограничений больший множитель x может являться как простым числом, так и составным. В последнем случае, для полученного не простого x, поиск составляющих простых множителей повторяется по выше описанной методике. Не существует зависимости количества составляющих простых множителей для числа от его размера или от количества составляющих его знаков.
Дополнительная практическая не вычислительная сложность использования не только данного метода при разложении на множители, но и любых других действий над большими числами заключается ещё и в  количестве составляющих знаков разбираемого числа. Не только простые действия с, например, 500-значными числами требуют значительных затрат времени, у меня вычисление корня квадратного из 600-значного числа занимает более часа времени, но и просто запись такого числа требует времени и усилий. Определение вычислительной сложности не меняется, и продолжает составлять всё те же менее (0,08√z). Но и 8% от такого числа является довольно ощутимым значением.
Для любого произвольного числа, помимо составляющих его простых множителей, всегда существует минимум одна пара связаных слагаемых a и b, удовлетворяющая требованиям:
            x = a + b
            y = a - b                                                                                                                    (3)
соответственно:
            a = ( x + y ) / 2
            b = ( x – y ) / 2                                                                                                          (4)
где x ≥ a > b; a ≠ b; a ≥ y.
Следовательно:
            z = x * y = ( a + b ) * ( a – b ) = a2 - b2                                                                     (5)
В рамках установленных ограничений из формул(4):
            a = ( x + y ) / 2 = ( нечетное целое + нечетное целое ) / 2 = ( четное целое ) / 2 = целое
            b = ( x – y ) / 2 = ( нечетное целое - нечетное целое ) / 2 = ( четное целое ) / 2 = целое
То есть, для любого нечетного числа всегда существует как минимум одна пара целых связаных слагаемых. Каждая пара связаных слагаемых определяет (задаёт, характеризует, генерирует) только одно число. Для некоторых четных целых чисел не всегда существует пара целых связаных слагаемых,  а только дробные, но, повторюсь, в рамках рассматриваемой задачи четные числа меня не интересуют.
Исходя из формул(4) можно определить диапазон изменения связаных слагаемых a и b: 
a ϵ ( √z ; (( z + 1 ) / 2 ) ), b ϵ ( 0 ; (( z – 1 ) / 2 ) ); 
xmin = ymax = amin = √z, bmin = 0, если √z имеет целое значение; 
xmax = z, ymin = 1, amax = ( ( z + 1 ) / 2 ), bmax = ( ( z – 1 ) / 2 ), если z простое число.
 Отсюда очевидно, что диапазоны изменения связаных слагаемых a и b значительно превышают диапазон изменения меньшего простого множителя y, что делает вычислительную сложность поиска их значений методом перебора не конкурентной, по сравнению с перебором возможных значений y.
Исходя из формулы(5), возможна реализация поиска значений связаных слагаемых для исследуемого числа графическим способом на основании теоремы Пифагора. Данный вариант осложнен условием, что в общем случае (√z) не является целым числом, но проверить несколько найденных пар потенциальных значений проще и быстрее, чем последовательный перебор всех значений. Кроме того, лично я не представляю, как оценивать и сравнивать вычислительную сложность данного метода при реализации его инструментами разных графических приложений и программ.
Общеизвестно, что все числа можно условно разделить на ряды кратности какому-либо числу, на которое они делятся нацело. Но целые числа, так же условно, можно разделить на несколько более сложно зависимые ряды условной кратности по связаным слагаемым – ряды чисел с одинаковым меньшим (или большим) связаным слагаемым. Ряд чисел с одинаковым меньшим связаным слагаемым b представляет собой бесконечную арифметическую прогрессию второго порядка: шаг прогрессии (h) у нее не постоянный, а является арифметической прогрессией с постоянным шагом 2. При этом:
            n = 2b + 1                                                                                                                 (6)
            b = ( n – 1 ) / 2,
где n – первый член z1 арифметической прогрессии второго порядка Z для исследуемого меньшего связаного слагаемого b, то есть первый член ряда кратных меньшему связаному слагаемому.
            d = 2 b + 3 = n + 2,                                                                                                   (7)
где d – первый член h1 арифметической прогрессии H, являющейся шагом арифметической прогрессии второго порядка Z для исследуемого меньшего связаного слагаемого b.
Приведу примеры, исходя из формул(3) и ограничения (a > b).

Для b = 0
a
x
y
z
h
1
1
1
1

2
2
2
4
3
3
3
3
9
5
4
4
4
16
7
5
5
5
25
9
6
6
6
36
11
7
7
7
49
13

Для b = 1
a
x
y
z
h
2
3
1
3

3
4
2
8
5
4
5
3
15
7
5
6
4
24
9
6
7
5
35
11
7
8
6
48
13
8
9
7
63
15

Для b = 2
a
x
y
z
h
3
5
1
5

4
6
2
12
7
5
7
3
21
9
6
8
4
32
11
7
9
5
45
13
8
10
6
60
15
9
11
7
77
17

Для b = 3
a
x
y
z
h
4
7
1
7

5
8
2
16
9
6
9
3
27
11
7
10
4
40
13
8
11
5
55
15
9
12
6
72
17
10
13
7
91
19

Отсюда: каждое нечетное число, и некоторые из четных, можно разложить на конечный ряд H последовательных нечетных чисел, меньший член которого равен n, количество членов этого ряда равно меньшему простому составляющему множителю y. Для нечетных чисел (а возможно, и для некоторых четных) составляющий множитель x является членом этой прогрессии с номером
            j = ( ( y – 1 ) / 2 )                                                                                                      (8)
при этом:
            x = n + 2j = n + y – 1                                                                                                (9)
При обычном делении из делимого z y раз вычитается число  x, то есть число z дробится на y частей одинакового размера x. По аналогии, с учетом, что любое нечетное число можно раздробить на y последовательно возрастающих частей, при ступенчатом делении, произвольное нечетное число z делится на y нечетных последовательно увеличивающихся частей, меньшая часть из которых равна n. Данный факт можно использовать для графической реализации поиска конечного ряда H последовательных нечетных чисел с помощью «ломаных» или «столбиков», но, повторюсь, лично я не представляю, как оценивать и сравнивать вычислительную сложность данного метода при реализации его инструментами разных графических приложений и программ. Аналитически данный способ факторизации чисел будет рассмотрен в Варианте_2.
Ряд условной кратности чисел Z большему связаному слагаемому a является конечным, ограниченным условиями (a > b), (a > 0).

Для a=1, zmin=zmax= a2 = 2a-1
b
x
y
z
h
0
1
1
1


Для a=2
b
x
y
z
h
0
2
2
4

1
3
1
3
1

Для a=3
b
x
y
z
h
0
3
3
9

1
4
2
8
1
2
5
1
5
3

Для a=4
b
x
y
z
h
0
4
4
16

1
5
3
15
1
2
6
2
12
3
3
7
1
7
5

Для a=5
b
x
y
z
h
0
5
5
25

1
6
4
24
1
2
7
3
21
3
3
8
2
16
5
4
9
1
9
7

Для a=6
b
x
y
z
h
0
6
6
36

1
7
5
35
1
2
8
4
32
3
3
9
3
27
5
4
10
2
20
7
5
11
1
11
9

Для a=7
b
x
y
z
h
0
7
7
49

1
8
6
48
1
2
9
5
45
3
3
10
4
40
5
4
11
3
33
7
5
12
2
24
9
6
13
1
13
11

Исходя из существующих ограничений, количество членов ряда условной кратности чисел Z большему связаному слагаемому равно i = a, z ϵ ( a2 ; 2a - 1). Сам ряд представляет собой прогрессию второго порядка и изменяется от максимального, равного z = a2 при b = 0, до минимального, равного z = ( 2a - 1) при b = (a - 1), с шагом в виде арифметической прогрессии с h = 2, минимальный член которой всегда равен 1. В отличие от ряда условной кратности меньшему связаному слагаемому b, где минимальный член зависит от b. Это дает возможность не искать перебором, а высчитать связаное слагаемое a для любого нечетного числа, зная только само число. К чему, собственно и пришел Ферма, только с более простой аргументацией.
   Вариант_1 - оказался методом факторизации Ферма.
Для этого необходимо выполнить определенный набор действий, не зависящий от величины числа:
 - вычислить c, равное amin, равное целой части корня квадратного  от исследуемого числа z;
 - сформировать таблицу квадратов чисел на промежутке от c = amin= (целая часть корня квадратного от z) до amax = (( z + 1 ) / 2), либо берем часть уже существующей таблицы;
 - последовательно наплюсовываем к z последовательные нечетные числа, начиная с 1. Каждую полученную сумму проверяем на наличие целого корня квадратного, сравнивая с данными в таблице квадратов. Наплюсованная сумма с целым корнем квадратным и является a2, сумма наплюсованных слагаемых – это и есть b2;
 - смотрим в таблице квадратов значение корня квадратного из вычисленного b2;
 - по формулам(3) определяем составляющие множители; 
  - всё, расчет закончен.
Вероятно, формирование таблицы квадратов и наплюсовывание к z последовательных нечетных чисел имеет смысл производить на разных вычислительных машинах параллельно. Для формирования таблицы квадратов можно пользоваться только действием сложения, не используя умножения.
   Вариант_2 - чужое авторство данного способа мне не известно. Прошу уведомить меня, если данный способ факторизации уже описан.
Задача разложения исследуемого числа z на составляющие его простые множители, исходя из свойств меньшего связаного слагаемого b, представляет собой поиск подмножества последовательных нечетных чисел, сумма которых равна исследуемому числу z. У данной задачи есть три случая развития решения.
1) Если исследуемое число z имеет целое значение корня квадратного √z=i=x=y. В этом случае, в соответствии со свойствами связаных слагаемых, b=0 и меньший член подмножества последовательных нечетных чисел, сумма которых равна исследуемому числу z, всегда равен единице. Тогда, решение задачи сведется к суммированию последовательных нечетных чисел, начиная с единицы, до достижения z=k=1+3+5+…+ ni. Это вычислительно самый простой частный случай, алгоритм решения которого содержит наименьшее количество действий.

Блок_1 . . . . . . . . . . . . . . . m=1,n=3,i=2,z,l=1
. .переход к блоку_2
Блок_2 . . . . . . . . . . . . . . . k=m+n
. .переход к блоку_3
Блок_3 . . . . . . . . . . . . . . . если z=k, то переход «да» к блоку_6, иначе переход «нет» к блоку_4
. .переход «нет» от блока_3 к блоку_4
Блок_4 . . . . . . . . . . . . . . . i=i+1,n=n+2
. .переход к блоку_5
Блок_5 . . . . . . . . . . . . . . . k=k+n
. .переход от блока_5 к блоку_3
. .переход «да» от блока_3 к блоку_6
Блок_6 . . . . . . . . . . . . . . . вывод данных, конец алгоритма

            Рис.1 - Блок-схема к варианту_1

2) Общий случай: исследуемое число z не имеет целого значения корня квадратного и неизвестно, является ли оно простым числом. В этом случае, в блок-схему алгоритма решения добавляется еще один критерий оценки состояния переменной k по отношению к исследуемому числу z и блок вычислений из трех действий. Суммирование последовательных нечетных чисел, начиная с единицы, продолжается до достижения z<k=1+3+5+…+ ni, после чего происходит последовательное уменьшение суммы последовательных нечетных чисел на меньший член подмножества или прибавление следующего нечетного числа, в зависимости от проверки соотношения значений исследуемого числа z и переменной k после каждого блока вычислений. Вычисления будут продолжаться до тех пор, пока значение переменной k не станет равным числу z и переменная i, являющаяся счетчиком количества суммированных последовательных нечетных чисел, примет значение, равное y – меньшему составляющему простому множителю исследуемого числа z. Этот вариант решения задачи разложения исследуемого числа z на составляющие его простые множители содержит больше вычислительных действий, чем в первом варианте, когда исследуемое число имеет целое значение корня квадратного. В худшем случае, вычисления будут продолжаться до i=3, nmax=((z/3)+2), так как, в соответствии с формулой(9): при y=3, x=(z/3)=n+y-1=n+3-1=n+2, тогда n=((z/3)-2)=n1, n2=n+2=(z/3), n3= n2+2=nmax=((z/3)+2).

Блок_1 . . . . . . . . . . . . . . . m=1,n=3,i=2,l=1,z
. .переход к блоку_2
Блок_2 . . . . . . . . . . . . . . . k=m+n
. .переход к блоку_3
Блок_3 . . . . . . . . . . . . . . . если z=k, то переход «да» к блоку_9, иначе переход «нет» к блоку_4
. .переход «нет» от блока_3 к блоку_4
Блок_4 . . . . . . . . . . . . . . . если z>k, то переход «да» к блоку_7, иначе переход «нет» к блоку_5
. .переход «нет» от блока_4 к блоку_5
Блок_5 . . . . . . . . . . . . . . . k=k-l,i=i-1
. .переход к блоку_6
Блок_6 . . . . . . . . . . . . . . . l=l+2
. .переход от блока_6 к блоку_3
. .переход «да» от блока_4 к блоку_7
Блок_7 . . . . . . . . . . . . . . . i=i+1,n=n+2
. .переход к блоку_8
Блок_8 . . . . . . . . . . . . . . . k=k+n
. .переход от блока_8 к блоку_3
. .переход «да» от блока_3 к блоку_9
Блок_9 . . . . . . . . . . . . . . . вывод данных, конец алгоритма

 

           Рис.2 - Блок-схема к варианту_2


3) Если исследуемое число z является простым числом, то вычисление алгоритма не останавливается при i=3, nmax=((z/3)+2) и продолжается до i=1, nmax=z. Вычислительно это самый сложный вариант решения задачи, поскольку проверяется в 3 раза больше значений переменной k. При добавлении после блока_7 критерия проверки n=((z/3)+4), с остановкой выполнения алгоритма при его выполнении и выведением соответствующего сообщения, отсекаются лишние бессодержательные повторения вычислительных действий, уравниваются вычислительная сложность худшего случая решения задачи в общем случае и вычислительная сложность решения задачи, когда число z является простым числом. 

Блок_1 . . . . . . . . . . . . . . . m=1,n=3,i=2,l=1,z
. .переход к блоку_2
Блок_2 . . . . . . . . . . . . . . . k=m+n
. .переход к блоку_3
Блок_3 . . . . . . . . . . . . . . . если z=k, то переход «да» к блоку_10, иначе переход «нет» к блоку_4
. .переход «нет» от блока_3 к блоку_4
Блок_4 . . . . . . . . . . . . . . . если z>k, то переход «да» к блоку_7, иначе переход «нет» к блоку_5
. .переход «нет» от блока_4 к блоку_5
Блок_5 . . . . . . . . . . . . . . . k=k-l,i=i-1
. .переход к блоку_6
Блок_6 . . . . . . . . . . . . . . . l=l+2
. .переход от блока_6 к блоку_3
. .переход «да» от блока_4 к блоку_7
Блок_7 . . . . . . . . . . . . . . . i=i+1,n=n+2
. .переход к блоку_8
Блок_8 . . . . . . . . . . . . . . . если n<((z/3)+4), то переход «да» к блоку_9, иначе переход «нет» к блоку_11 
. .переход «да» от блока_8 к блоку_9
Блок_9 . . . . . . . . . . . . . . . k=k+n
. .переход от блока_9 к блоку_3
. .переход «да» от блока_3 к блоку_10
Блок_10 . . . . . . . . . . . . . . . вывод данных, конец алгоритма
. .переход «нет» от блока_8 к блоку_11
Блок_11 . . . . . . . . . . . . . . . вывод данных, конец алгоритма

          Рис.3 - Блок-схема к варианту_3

Конечным искомым решения задачи является определение количества i членов подмножества последовательных нечетных чисел, дающих в сумме значение исследуемого числа z, либо выведение сообщения о том, что оно является простым.

Решение задачи поиска подмножества последовательных нечетных чисел, сумма которых равна исследуемому числу z, можно реализовать и при помощи табличного приложения, например Excel.  Создаются два столбца. В одном столбце, например А, ячейки заполняются сверху вниз последовательными нечетными числами по возрастанию от 1 до ((z/3)+4) – для предотвращения лишних итераций когда число z является простым числом. В соседнем столбце, например В, в ячейки, кроме верхней, вписываются формулы. Так, пусть ячейка А1 – пустая, в ячейке В1 записывается значение z. Тогда, А2=1, А3=3, А4=5 и так далее. В остальные ячейки столбца В записывается формула «=(ячейка сверху)минус(ячейка слева)». В ячейке В2 записывается формула «=В1-А2», в ячейке В3 записывается «=В2-А3», и так далее. После формирования столбцов выполняются формулы и проверяется, принимает ли какая-либо ячейка в столбце В значение «ноль». Если «да», то вычисления закончены - это случай_1 развития решения задачи,- определяется количество не пустых ячеек в столбце А от строки, в которой формула в ячейке столбца В приняла значение «ноль», и в вверх до ячейки А1 включительно. Иначе, продолжается поиск последовательных нечетных чисел, сумма которых равна исследуемому числу z. Для этого удаляется самое верхнее, наименьшее нечетное число в столбце А и проверяется, принимает ли какая-либо ячейка в столбце В значение «ноль». Если «да», то вычисления закончены, если «нет», то удаление верхнего нечетного в столбце А и проверка столбца В повторяется до тех пор, пока какая-либо ячейка в столбце В примет значение «ноль» либо до удаления последнего нечетного числа в столбце А, равного ((z/3)+4) – что значит, что число z является простым числом. С помощью макросов весь описанный процесс в табличном приложении Excel полностью программируется и выполняется автоматически.
Также этот алгоритм можно выполнять в табличном приложении Excel в более развернутом виде.
Для удобства пользователя, верхние три строки закрепляются. Сначала, ставим рабочие пометки: в ячейке C1 пишем «z», в ячейке E1 пишем «-», в ячейке G1 пишем «+», в ячейке I1 пишем «z-+». Затем:
- в ячейку C2 записываем исследуемое число z;
- в ячейку E2 записываем формулу «=сумм(D:D)» - формула возвращает сумму всех чисел в ячейках столбца D;
- в ячейку G2 записываем формулу «=сумм(F:F)» - формула возвращает сумму всех чисел в ячейках столбца F;
- в ячейку I2 записываем формулу «=C2-E2+G2» - формула уменьшает исследуемое число на величину суммы чисел в ячейках столбца D и увеличивает полученную разницу на величину суммы чисел в ячейках столбца F – основной вычислительный процесс;
- в ячейку E3 записываем формулу «=счёт(D:D)» - формула возвращает количество не пустых ячеек столбца D – перебор величины связаного слагаемого a;
- в ячейку G3 записываем формулу «=счёт(F:F)» - формула возвращает количество не пустых ячеек столбца F – перебор величины связаного слагаемого b;
- в ячейку I3 записываем формулу «=E3-G3» - формула считает разницу между количеством не пустых ячеек столбца D и количеством не пустых ячеек столбца F – разницу между текущей величиной связаного слагаемого a и текущей величиной связаного слагаемого b, то есть перебор величины меньшего составляющего множителя y;
- в ячейку K3 записываем формулу «=E3+G3» - формула считает суммарное количество не пустых ячеек столбца D и не пустых ячеек столбца F – сумму текущей величины связаного слагаемого a и текущей величины связаного слагаемого b, то есть перебор величины большего составляющего множителя x.
 Данный вариант реализации алгоритма решения исследуемой задачи более информативен, чем рассматриваемый ранее, и позволяет, как избежать постоянного перемещения от начала подмножества последовательных нечетных чисел в его конец, опять в начало и так далее, так и отсечь, при необходимости, вспомогательные вычислительные действия. Для выполнения решения, в ячейки столбца D в порядке сверху вниз вносятся последовательные нечетные числа, в порядке возрастания, начиная с единицы, до тех пор, пока в ячейке I2 не появится ноль, либо отрицательное число. Если на данном этапе выполнения решения в ячейке I2 появится ноль, значит, исследуемое число z имеет целое значение корня квадратного, и значения в ячейках будут иметь следующий вид: E3=a=I3=y=K3=x – они будут равны значению корня квадратного из числа z, в ячейке G3=b=0. Если же на данном этапе выполнения решения в ячейке I2 появится отрицательное число, то в ячейки столбца F в порядке сверху вниз вносятся последовательные нечетные числа, в порядке возрастания, начиная с единицы, до тех пор, пока в ячейке I2 не появится ноль, либо положительное число. Теперь получение нуля ячейке I2 будет свидетельствовать о нахождении таких значений E3=a и G3=b, что ((E3=a)-(G3=b)=(I3=y)) и ((E3=a)+(G3=b)=(K3=x)), при которых ((I3=y)*(K3=x)=(C2=z)=(E2-G2)). В дальнейшем решении выполняется правило: если в ячейке I2 появляется отрицательное число, то вносим в следующую по порядку ячейку столбца F следующее по порядку нечетное число, если в ячейке I2 появится положительное число, то вносим в следующую по порядку ячейку столбца D следующее по порядку нечетное число. Так должно продолжаться до появления в ячейке I2 нуля, свидетельствующего об окончании вычислений, или до появления в ячейке I3=y значения 2, свидетельствующего о том, что исследуемое число z является простым, и дальнейшие вычисления нецелесообразны.
Как видно из описания выполняемых действий, вычислительная сложность решения задачи поиска подмножества последовательных нечетных чисел, сумма которых равна исследуемому числу z, она же задача разложения исследуемого числа z на составляющие множители, по сути, одинакова для различных вариантов развития решения:
1) Если исследуемое число z имеет целое значение корня квадратного. В этом случае от исследуемого числа z будет (E3=a=I3=y=K3=x=√z)-раз произведено вычитание.
2) Если исследуемое число z не имеет целое значение корня квадратного. В этом случае от исследуемого числа z будет (K3=x)-раз произведено вычитание и сложение.
3) В случаях, если исследуемое число z оказывается простым числом, продолжительность вычислений, количество вычислительных действий, зависит от того, как настроен стоп-маркер. Это может быть значение c=((z/3)+4), либо появление в ячейке I3=y значения 2, либо что-либо еще. В любом случае, вычислительная сложность данного варианта решения будет порядка ((z/3)+2). 
01.2008г. - 21.07.2018г.
Автор: на Комментариев нет:
Подписаться на: Сообщения (Atom)