О существовании точного метода факторизации составных чисел

Предложен метод факторизации составных чисел по принципу цифра за цифрой, позволяющий за конечное число шагов найти сомножители благодаря теоретико-числовым представлениям систем счисления. Метод позволяет решать диофантовы уравнения, а также получать точный тест простоты чисел. A method of the fact...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Veröffentlicht in:	Управляющие системы и машины
Datum:	2011
1. Verfasser:	Семотюк, М.В.
Format:	Artikel
Sprache:	Russisch
Veröffentlicht:	Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України 2011
Schlagworte:	Фундаментальные и прикладные проблемы Computer Science
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/83003
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	О существовании точного метода факторизации составных чисел / М.В. Семотюк // Управляющие системы и машины. — 2011. — № 6. — С. 3-9. — Бібліогр.: 7 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

_version_	1860270782079303680
author	Семотюк, М.В.
author_facet	Семотюк, М.В.
citation_txt	О существовании точного метода факторизации составных чисел / М.В. Семотюк // Управляющие системы и машины. — 2011. — № 6. — С. 3-9. — Бібліогр.: 7 назв. — рос.
collection	DSpace DC
container_title	Управляющие системы и машины
description	Предложен метод факторизации составных чисел по принципу цифра за цифрой, позволяющий за конечное число шагов найти сомножители благодаря теоретико-числовым представлениям систем счисления. Метод позволяет решать диофантовы уравнения, а также получать точный тест простоты чисел. A method of the factoring of the composite numbers is suggested on the basis of digit by digit that makes it possible, by the finite number of steps to find the factors due to the number-theoretic concepts of the number systems. The method allows to solve Diophantine equations, as well as to get an accurate test for primality. Запропоновано метод факторизації складених чисел за принципом цифра за цифрою, що дозволяє за скінченне число кроків знайти співмножники завдяки теоретико-числовому представленню систем числення. Метод дозволяє розв’язувати діофантові рівняння та одержувати точний тест простоти чисел.
first_indexed	2025-12-07T19:06:32Z
format	Article
fulltext	УСиМ, 2011, № 6 3 Фундаментальные и прикладные проблемы Computer Science УДК 512(075) М.В. Семотюк О существовании точного метода факторизации составных чисел Предложен метод факторизации составных чисел по принципу цифра за цифрой, позволяющий за конечное число шагов най- ти сомножители благодаря теоретико-числовым представлениям систем счисления. Метод позволяет решать диофантовы уравнения, а также получать точный тест простоты чисел. A method of the factoring of the composite numbers is suggested on the basis of digit by digit that makes it possible, by the finite num- ber of steps to find the factors due to the number-theoretic concepts of the number systems. The method allows to solve Diophantine equations, as well as to get an accurate test for primality. Запропоновано метод факторизації складених чисел за принципом цифра за цифрою, що дозволяє за скінченне число кроків знайти співмножники завдяки теоретико-числовому представленню систем числення. Метод дозволяє розв’язувати діофантові рівняння та одержувати точний тест простоти чисел. Введение. Отыскание простых множителей на- турального числа называют для краткости «фак- торизацией». Факторизация больших чисел – чрезвычайно трудоемкая задача, даже с помо- щью электронных вычислительных машин. C = a.b. (1) Полагая a = x + y, b = x – y имеем C = x2 – y2. Ферма – один из создателей теории чисел – в своих вычислениях пользовался, несомненно, этим свойством. Прием, основанный на этом свойстве, называют «факторизацией по разно- сти квадратов» и требует подбора квадратных чисел x2 и y2. Как прием факторизации можно использо- вать известный алгоритм Эвклида для отыска- ния наибольшего общего делителя (НОД) двух чисел. Однако он тоже требует подбора подхо- дящего числа. Возникает вопрос – можно ли сразу, по виду числа C, определить такое вспомогатель- ное число точно без использования процедур подбора. Постараемся ответить на этот во- прос положительно. Для этой цели рассмот- рим такое понятие числового множества, как структура.  Ключевые слова: факторизация, теоретико-число- вое преобразование, системы счисления, свертка. Постановка задачи Под структурой или решеткой [1–4] пони- мают частично упорядоченное множество, где каждое двухэлементное подмножество имеет (необходимо единственные) точную верхнюю и точную нижнюю грани. Отметим, что если это подмножество имеет только одну из точных граней, то его называют полуструктурой (верх- ней или нижней в зависимости от того, какая из точных граней существует). При этом струк- тура может быть получена из полуструктур, на- пример, путем пересечения, вычитания нижней полуструктуры из верхней либо каким-нибудь иным путем. В качестве верхней и нижней грани такого множества, именуемой структурой и обознача- емой в дальнейшем через S, наиболее часто используют выражения вида sup S = sup{a, b} = max(a + b), (2) inf S = inf {a, b} = min(a.b). (3) Хотя эти выражения и ограничивают мощ- ность несущего множества, но, так или иначе, они связаны с операциями, заданными той или иной алгеброй. Желательно иметь одно «уни- версальное» несущее множество, на котором возможно было бы задать не одну единствен- ную, следуя принципу замкнутости, алгебру, а некоторое их множество. Эта цель может быть 4 УСиМ, 2011, № 6 достигнута, если точные грани структуры, как несущего множества, задать следующим обра- зом [5]: supS = sup{a, b} = max[(ab) mod M] = M – 1, (4) infS = inf{a, b} = min[intp(ab)] = 0. (5) где  – знак произвольной алгебраической опе- рации, результат которой ограничен сверху опе- рацией по модулю M, а саму же операцию по модулю будем рассматривать как некоторую функцию, зависящую от M. intp() – функция, определяемая как целая часть по отношению к числу p,   1int intp x x p        . Если p = 1, то эта функция принимает тра- диционные представления, в другом случае, она отмечает тот факт, что целая часть существует не только при делении целых чисел, но и дроб- ных и т.п. Заметим, что функция ) (int p может быть представлена как 1int ( ) modp A A A M p   , (6) где A – результат той или иной операции. Из последнего утверждения следует, что структура, заданная выражениями (4, 5), полу- чена из двух полуструктур, верхняя грань од- ной из которых задана модулем M, а нижняя грань другим модулем M1, поэтому введено но- вое определение точных граней структуры. При этом такую структуру, задаваемую выражени- ями (4, 5), в дальнейшем будем называть ма- шинной структурой, понимая под этим терми- ном не технический термин, а математический. Из последних выражений следует, что, с одной стороны, такое определение структуры доста- точно полно согласуется с теми числовыми мно- жествами, которые задаются разрядной сеткой ЭВМ. С другой стороны, существует достаточ- но основательно разработанная математичес- кая теория вычетов, составляющая фундамен- тальную базу теоретико-числовых подходов в математике. Основными аксиоматическими по- ложениями этой теории есть алгебры вычетов по модулю, такие как кольцо вычетов, группа вычетов, поле вычетов, поле Галуа, а также пространства, оболочки, построенные либо над кольцом вычетов, либо над полем вычетов или групповые алгебры вычетов и их конструкции. Однако остается не выясненным вопрос, чем придется поступиться и с какими трудностями сталкиваться при использовании на практике, определенных таким образом, машинных струк- тур. Для этого рассмотрим такой случай. Пусть кольцо вычетов по единственному мо- дулю задано алгеброй вида Zm = <S, +, ., 0, 1> , (7) где Zm – здесь и далее кольцо вычетов по един- ственному модулю M, S – несущее множество, представляющее собой структуру, заданную выражениями (3, 4), в которых p = 1, +, . – ос- новные операции кольца, 0, 1 – нейтральные элементы операций сложения и умножения со- ответственно. При этом формально считается, что 0 ≠ 1, т.е. нейтральные элементы операции сложения и умножения различны. Но на практике это условие не всегда выполнимо, например, до- полнительный код в ЭВМ, а в других случаях является даже необходимым условием, напри- мер, булева алгебра. Если предположить, что 0 = 1, т.е. нейтральные элементы операций сло- жения и умножения совпадают и равны едини- це, то возникает двойственность. Действитель- но, пусть a + a' = 1, (8) где a' – обратный элемент для a по отношению к операции сложения (дополнение до 1). Тогда для кольца (7) получим a + a' = M + 1. (9) Далее, используя правила де Моргана, имеем (a'.b') = M + 1 – (M + 1 – a).(M + 1 – b) = = M + 1 – M 2 – 2M – 1 + Ma + a + Mb + b – ab. Окончательно, для кольца вычетов по моду- лю M в соответствии с верхней гранью струк- туры (3) получим )(  ba mZ abba  , (10) где mZ – означает тот факт, что вычисления вы- полняются в кольце вычетов Zm и как в левой УСиМ, 2011, № 6 5 части равенства, так и в правой, ограничены сверху величиной модуля M и принадлежат множеству S . Полученное выражение известно в литерату- ре как звездное произведение [6]. Таким обра- зом, установлено, что операции кольца вычетов Zm (сложение и умножение), заданные на струк- туре, могут быть двойственны, т.е. могут быть определены двумя различными путями либо, при одних и тех же условиях, возможно полу- чение двух различных результатов одной и той же операции. Следует заметить, что результа- ты вычислений в алгебрах вычетов и обычных алгебрах могут не совпадать, если не будут приняты соответствующие меры их коррекции. Рассмотрим еще один частный случай звезд- ного произведения ba  = (M – a).b = M.b – a.b. (11) Очевидно, что такое составное число и есть подходящим числом для алгоритма Эвклида. Действительно, пусть C = a.b=7.5 = 35, М = 10. Тогда согласно (11) имеем M.b – a.b = 10.5 – – 7.5 = 15, а числа 35 и 15 имеют общий мно- житель 5. С другой стороны, – C = –(a.b) = M 2 – (a.b), (12) представляет собой дополнение произведения a.b до модуля M 2 и отличается в кольце выче- тов по модулю M 2 от (11) на величину M.b, ко- торую следует вычесть в выражении (11) для того, чтобы получить верный результат. В ма- шинной арифметике этот прием называют кор- рекцией умножения. Далее полагая, что М = pN и M 2 = p2N имеем для кольца вычетов по модулю M 2 два числа – C mZ pk .b – (a.b), C mZ (a.b). Очевидно, величину pn.b вычислить не воз- можно, так как неизвестно b. Однако, полагая, что p – основание некоторой системы счисле- ния, а модуль кольца равен pN, имеем – C mZ – (a.b) = a'.b, C mZ (a.b), (13) М = pN, где a' – дополнение до модуля числа a. Отсюда следует, что мы имеем точные млад- шие части двух разных чисел с разрядностью N, которые имеют общий множитель. Заметим, что к системе (13) применим алгоритм Эвкли- да, если вычисления выполнять в кольце выче- тов Zm. Однако в этом случае некоторого пере- бора вариантов не избежать. О точном методе факторизации составных чисел Покажем теперь, что существует точный ме- тод факторизации составных чисел, не требую- щий перебора вариантов, и сформулируем сле- дующее утверждение. Утверждение 1. Для любого составного чис- ла С, которое представляет собой произведе- ние вида C = a.b, где a и b простые числа боль- ше 2, в силу единственности разложения его на простые множители, существует точный вычис- лительный метод его факторизации с конечн- ми вычислительными затратами. Докажем это утверждение. Для этого сначала рассмотрим фундамен- тальную теорему обобщенных теоретико-число- вых преобразований. Ее фундаментальный ха- рактер обусловлен тем, что с ее помощью до- казывается весь комплекс теорем этих преоб- разований без исключения. Доказательство тео- ремы приведено в [5]. Пусть алгебра вида Zm = <S, +, ., 0, 1>, где (0 ≠ 1) и ZS – структура (решетка), имею- щая supS = max[(ab)mod M] = sp – 1 и infS = = min[intp(ab)] = 0, представляет собой кольцо вычетов Zm с единицей, в котором своими ар- гументами задана степенная зависимость y = s x. Тогда для Ss , Np , 0,x N  и Np  существует такое число М, равное     1 0 N m msM < < supS, при котором в кольце вычетов Zm имеет место следующее соотношение: s(x)mod N mZ (sx)mod M, (14) где mZ – обозначает «имеет место» равно или сравнимо в кольце вычетов в общем случае не 6 УСиМ, 2011, № 6 всегда совпадающее с известным понятием «сравнение по модулю» в силу разных значе- ний модуля в левой и правой частях выраже- ния. В правой части целое выражение, ограни- ченное модулем М, а в левой части ограничен только показатель степени модулем N. Модуль М при этом есть функция от переменных s и N – M = f(s,N). Полагая теперь, что главное значение чи- словой степенной последовательности находит- ся на закрытом интервале [0, p – 1] = [0, N – 1], а Ssup 1 0 N m m M s    есть модуль кольца mZ , оп- ределим формально следующее преобразова- ние, заданное на структуре s X(k) mZ    1 0 N i N)ki(six mod)( , (15) x(i) mZ    1 0 1 N k NkiskX N mod)()( , (16)     1 0 N m msM , где N – некоторое число из множества N, x(i), ( )X k – числовые последовательности, пред- ставляющие оригинал и изображение соответ- ственно, s – некоторое число, в общем случае комплексное, i, k – номера (индексы) компо- нент последовательностей, а выражение (15) представляет собой прямое преобразование, (16) – обратное. Это преобразование в работе [5] названо обобщенным теоретико-числовым преобразо- ванием или S-преобразованием (преобразование задано на структуре, решетке S). Обобщен- ный характер этого преобразования вытекает из того, что модуль кольца 1 0 N m m M s     – не всегда простое число и разлагается на мно- жители, которые в свою очередь могут быть модулями преобразования Ферма, Мерсена, Гаусса или им подобным. Покажем одно важ- ное свойство этого преобразования. Для этой цели взвесим оригинал последовательностью вида w(i) = {0, 1, 0,..., 0}, (17) вычислим S-преобразование и сузим верхнюю и нижнюю грани структуры следующим образом {int()} mod s. Тогда будем иметь X(k) mZ 1 ( )mod 0 {int[ ( ) ( ) ]}mod , N ki N i x i w s s     i x(i) mZ 1 ( ) mod 0 1 ( ) N ki N k X k s N    , (18) 1 0 N m m M s     . Проанализируем (18). Из (16) следует, что w(i) = 1 при i = 1 и w(i) = 0, если i  1. Тогда x(i)w(i) = x(1), если i = 1, и x(i)w(i) = 0, если i  1. И, следовательно, (18) можно переписать X(k) mZ sswx i Nk ]}mod)()({int[ )mod(1   1 1 , x(i) mZ 1 ( )mod 0 ( ) , N ki N k X k s    только для i = 1, (19)     1 0 N m msM . Теперь полагая в (19) s = p, где p – основание системы счисления, i = 1, x(1) = A, где A N – число, принадлежащее множеству N, для кото- рого supS =     1 0 N m mpM (т.е. верхняя грань мно- жества N совпадает с модулем кольца вычетов Zm) и, учитывая, что w(1) = 1, получим X( k) mZ ppA Nk mod]}{int[ mod)( , A mZ    1 0 N k NkipkX )mod()( , только для i = 1, (20)     1 0 N m mpM Nsup . Из (19) следует, что представление чисел в какой-либо системе счисления – частный слу- чай обобщенного теоретико-числового преобра- зования, которое для краткости назовем Р-пре- образованием [7]. Отсюда делаем вывод, что позиционные системы счисления обладают всеми свойствами представлений в алгебраи- УСиМ, 2011, № 6 7 ческом смысле этого слова. Представляю- щим пространством, в котором описывается любое число из множества N, является про- странство, построенное над кольцом вычетов Zm, X(k) – суть цифры в разрядах системы счис- ления с основанием p, в которой представля- ется это число и которые теперь можно оп- ределить в любом интересующем нас поряд- ке. Отсюда следует главный вывод о таком представлении – значение цифры в любом раз- ряде любой системы счисления не зависит от значения цифры в других разрядах этого пред- ставления, например, число 37. Нас интересу- ет значение цифры во втором разряде двоич- ной системы счисления. Его двоичный код 100101. Вычислим преобразование для ин- декса k = 2. X(2) mZ (2)mod{int[37 2 ]}mod2 1N  . Для k = 3, X(3) mZ (3)mod{int[37 2 ]}mod2 0N  и т.д. Таким образом, существует возможность соз- дать «теорию» одного разряда. Далее, теоретико-числовое преобразование является изоморфным преобразованием и для него существует ряд теорем, в том числе и теорема о свертке изображения. Поэлементное произведение двух последо- вательностей–оригиналов в кольце вычетов mZ приводит к свертке их изображений: )()( iyix  Zm ),()( kYkX (21) где * – (здесь и ниже) обозначение свертки как оператора, Zm – означает «приводит» в кольцо вычетов mZ к такой-то зависимости. Очевидно, что действие теоремы распро- страняется и на частные случаи этого преоб- разования. Оно имеет место и в нашем слу- чае. Действительно, если же в (21)  X k и  Y k – суть цифры некоторой системы счис- ления     ,k kX k a Y k b  , а размерность пре- образования увеличим до 2N, чтобы полу- чить апериодическую свертку, имеем в мат- ричной записи * * * * 0 2 13 3 21 0 02 1 3 2 1 0 02 13 3 2 1 0 02 13 3 2 1 0 0 0 00 1 0 1 1 01 2 02 33 4 5 6 7 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 00 0 000 0 0 0 0 0 0 0 0 0 a a aa a aa a aa a a a a a aa aa a a a a aa aa a a a a S a bb S a b a bb S ab Sb S S S S                                                * * * * * * * * * * * * 2 1 1 2 0 0 3 1 2 2 1 3 0 1 3 2 2 3 1 2 3 3 2 3 3 , 0 b a b a b a b a b a b a b a b a b a b a b a b a b                         (22) где Sk – коэффициенты свертки, а для примера N = 3. Очевидно также, что коэффициенты свертки Sk не совпадают с цифрами Ck в разрядах пред- ставления числа C в той или иной системе счис- ления, поскольку значения этих коэффициентов превышают основание системы счисления, т.е. S k > p. Однако значения Ck можно вычислить, осуществив сначала обратное, а затем прямое Р – преобразование в соответствии с выраже- ниями (20). с(k) mZ 1 ( )mod ( )mod 0 {int[( ( ) ) ]}mod N ki N k N k X k p p p     , или учесть влияние переносов традиционным способом с учетом возможностей Р – преобразо- вания о независимости образования цифр в раз- рядах системы счисления следующим образом: 0 0( )mod ,с S p 11 1 0( int ) mod , p с S S p  2 22 2 0 1( int int )mod , p p с S S S p   3 3 33 3 0 1 2( int int int )mod , p p p с S S S S p    4 4 4 4 4 4 0 1 2 3 ( int int int int ) mod , p p p p ñ S S S S S p       5 5 5 5 5 5 5 0 1 2 3 4 ( int int int int int )mod , p p p p p с S S S S S S p        8 УСиМ, 2011, № 6 6 6 6 6 6 6 6 6 0 1 2 3 4 5 ( int int int int int int )mod , p p p p p p с S S S S S S S p         7 7 7 7 7 7 7 7 7 0 1 2 3 4 5 6 ( int int int int int int int )mod , p p p p p p p с S S S S S S S S p          где int k lp S – перенос в k-й разряд от l-го коэф- фициента свертки. Поскольку из (13) мы имеем только N точ- ных разрядов этих чисел, то размерность сверт- ки можно сократить до N * * * * * * * * * * 0 0 0 1 0 1 1 2 1 0 2 2 3 33 2 1 0 0 0 0 1 1 0 0 2 1 1 2 0 0 3 1 2 2 1 3 0 0 0 0 0 0 0 , a b S a a b S a a a b S b Sa a a a a b a b a b a b a b a b a b a b a b a b                                            0 0( )mod ,с S p (23) 11 1 0( int ) mod , p с S S p  2 22 2 0 1( int int )mod , p p с S S S p   3 3 33 3 0 1 2( int int int )mod . p p p с S S S S p    Запишем эти же выражения (23) для перво- го числа из (13) , т.е. через дополнение числа a * * * * * * * * * * 0 0 1 0 1 2 1 0 2 33 2 1 0 0 00 0 1 1 01 0 2 1 1 2 02 3 0 3 1 2 2 1 3 0 0 0 0 0 0 0 , a b a a b a a a b ba a a a a bS a b a bS a b a b a bS S a b a b a b a b                                                       0 0( )m od ,с S p  11 1 0( int ) mod , p с S S p    2 22 2 0 1( int int )mod , p p с S S S p      3 3 33 3 0 1 2( int int int )mod , p p p с S S S S p        где ,i iс S  – суть цифры соответствующих до- полнений чисел c и S. Теперь найдем разность между вторым и первым числом выражения (13) * * * * * * 0 0 0 0 0 1 1 0 1 1 1 2 2 1 1 0 0 2 2 2 3 3 33 3 2 2 1 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 2 1 1 1 2 2 0 0 0 0 0 0 ( ) ( ) ( ) ( ) ( ) ( ) a a b S S a a a a b S S a a a a a a b S S b S Sa a a a a a a a a a b a a b a a b a a b a a b a a b                                                              * * * * 0 0 0 0 3 1 1 1 2 2 2 1 3 3 0 , ( ) ( ) ( ) ( - )a a b a a b a a b a a b                 0 0 0 0[ ]mod ,c c S S p   (24) 11 1 1 1 0 0[ int ( )]mod , p c c S S S S p      2 2 2 2 2 2 0 0 1 1 c c [ int ( ) int ( )]mod , p p S S S S S S p           3 3 3 3 3 3 3 0 0 1 1 2 2 [ int ( ) int ( ) int ( )]mod . p p p c c S S S S S S S S p             Полагая, что р = 2 (т. е. система счисления двоичная) можно записать логические выра- жения для (24) следующим образом с учетом возможного переполнения 0 – – – – – 0 1 1 2 2 3 3 4 4 0 0 0 0 0 1 1 1 0 0 0 2 1 1 1 2 2 0 0 0 3 1 1 2 2 2 1 3 3 0 1 1 3 2 2 2 3 3 1 ( )& ( )& ( )& ( )& ( )& ( )& ( )& ( )& ( )& ( )& ( )& ( )& ( )& S S S S S S S S S S a a b a a b a a b a a b a a b a a b a a b a a b a a b a a b a a b a a b a a b                                             .       В правой части полученного равенства вы- ражение ii aa  , силу свойств двоичного до- полнительного кода, для всех 0i  равно 1, а при i = 0 равно 0. Тогда имеем 00 0 1 01 1 2 1 02 2 3 3 3 2 1 0 4 4 3 2 1 0& 0& 1& 0& 1& 1& 0& 1& 1& 1& 1& 1& 1& bS S b bS S b b bS S S S b b b b S S b b b                                  или УСиМ, 2011, № 6 9 0 0 01 1 1 02 2 2 1 03 3 3 2 14 4 0 . S S bS S b bS S b b bS S b b bS S                            Заметим, что матричные записи выражений здесь и выше, если говорить языком машинной арифметики, только иллюстрируют процесс об- разования частичных произведений. Точные же значения цифр разрядов определяются всегда с учетом переносов 0 0 1 2 2 3 3 3 3 3 1 1 0 0 0 2 2 1 0 0 0 1 1 3 3 2 1 0 0 0 1 1 2 2 3 3 3 2 1 1 1 2 2 [0]mod , [ int ( )]mod , [ int ( ) int ( )]mod , [ int ( ) int ( ) int ( )]mod , [ int ( ) int ( ) p p p p p p p p c c p c c b S S p c c b b S S S S p c c b b b S S S S S S p c c b b b S S S S                                        3 3 3int ( )]mod . p S S p          (25) Полученная запись (25) представляет собой систему логических уравнений, в которой ка- ждое уравнение содержит только цифры соот- ветствующих разрядов одного и того же числа b и переносы в этот же разряд. Решение этой системы не имеет каких-либо трудностей, по- скольку эти уравнения представляют собой так называемую «хвостовую» рекурсию. Так из вто- рого уравнения легко определяется b0, из треть- его – b1 и т.д. Такой метод решения обычно называют методом цифра за цифрой из-за того, что на каждом этапе определяется одна только цифра числа b. Отсюда следует, что действи- тельно существует точный метод факторизации, требующий для своей реализации всего лишь log2N/2 шагов вычислений, где N – разрядность числа С в двоичной системе счисления. Заключение. Таким образом, впервые в прак- тике теории чисел, доказано существование точ- ного метода факторизации составных чисел. Ме- тод относится к классу методов цифра за циф- рой и имеет конечное число шагов (итераций) для своей реализации, равное log2N/2. Его при- менение на практике позволит решать многие задачи факторизации составных чисел в крип- тографии, решать диофантовы уравнения, а так- же создать точные тесты простоты чисел. 1. Фрид Э. Элементарное введение в абстрактную ал- гебру. – М.: Мир, 1979. – 230 с. 2. Скорняков Л.А. Элементы алгебры. – М.: Наука, 1966. – 240 c. 3. Поспелов Д.А. Логические методы анализа и синте- за схем. – М.: Энергия, 1974. – 366 с. 4. Корн Г., Корн Т. Справочник по математике. – М.: Наука, 1973. – 632 с. 5. Семотюк М.В. Обобщенное теоретико-числовое пре- образование. – К.: 1994. – 30 с. (Препринт/НАН Ук- раины, Ин-т кибернетики им. В.М. Глушкова; 94–6). 6. Ван дер Варден Б.Л. Алгебра. – М.: Наука, 1979. – 624 с. 7. Семотюк М.В. Теоретико-числовые представления систем счисления // УСиМ. – 2004. – № 5. – С. 36–42. Поступила 07.09.2011 Тел. для справок: (044) 526-0656 (Киев) E-mail: semo@i.ua © М.В. Семотюк, 2011  Внимание ! Оформление подписки для желающих опубликовать статьи в нашем журнале обязательно. В розничную продажу журнал не поступает. Подписной индекс 71008 << /ASCII85EncodePages false /AllowTransparency false /AutoPositionEPSFiles true /AutoRotatePages /None /Binding /Left /CalGrayProfile (Dot Gain 20%) /CalRGBProfile (sRGB IEC61966-2.1) /CalCMYKProfile (U.S. Web Coated \050SWOP\051 v2) /sRGBProfile (sRGB IEC61966-2.1) /CannotEmbedFontPolicy /Error /CompatibilityLevel 1.4 /CompressObjects /Tags /CompressPages true /ConvertImagesToIndexed true /PassThroughJPEGImages true /CreateJobTicket false /DefaultRenderingIntent /Default /DetectBlends true /DetectCurves 0.0000 /ColorConversionStrategy /CMYK /DoThumbnails false /EmbedAllFonts true /EmbedOpenType false /ParseICCProfilesInComments true /EmbedJobOptions true /DSCReportingLevel 0 /EmitDSCWarnings false /EndPage -1 /ImageMemory 1048576 /LockDistillerParams false /MaxSubsetPct 100 /Optimize true /OPM 1 /ParseDSCComments true /ParseDSCCommentsForDocInfo true /PreserveCopyPage true /PreserveDICMYKValues true /PreserveEPSInfo true /PreserveFlatness true /PreserveHalftoneInfo false /PreserveOPIComments true /PreserveOverprintSettings true /StartPage 1 /SubsetFonts true /TransferFunctionInfo /Apply /UCRandBGInfo /Preserve /UsePrologue false /ColorSettingsFile () /AlwaysEmbed [ true ] /NeverEmbed [ true ] /AntiAliasColorImages false /CropColorImages true /ColorImageMinResolution 300 /ColorImageMinResolutionPolicy /OK /DownsampleColorImages true /ColorImageDownsampleType /Bicubic /ColorImageResolution 300 /ColorImageDepth -1 /ColorImageMinDownsampleDepth 1 /ColorImageDownsampleThreshold 1.50000 /EncodeColorImages true /ColorImageFilter /DCTEncode /AutoFilterColorImages true /ColorImageAutoFilterStrategy /JPEG /ColorACSImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /ColorImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /JPEG2000ColorACSImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /JPEG2000ColorImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /AntiAliasGrayImages false /CropGrayImages true /GrayImageMinResolution 300 /GrayImageMinResolutionPolicy /OK /DownsampleGrayImages true /GrayImageDownsampleType /Bicubic /GrayImageResolution 300 /GrayImageDepth -1 /GrayImageMinDownsampleDepth 2 /GrayImageDownsampleThreshold 1.50000 /EncodeGrayImages true /GrayImageFilter /DCTEncode /AutoFilterGrayImages true /GrayImageAutoFilterStrategy /JPEG /GrayACSImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /GrayImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /JPEG2000GrayACSImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /JPEG2000GrayImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /AntiAliasMonoImages false /CropMonoImages true /MonoImageMinResolution 1200 /MonoImageMinResolutionPolicy /OK /DownsampleMonoImages true /MonoImageDownsampleType /Bicubic /MonoImageResolution 1200 /MonoImageDepth -1 /MonoImageDownsampleThreshold 1.50000 /EncodeMonoImages true /MonoImageFilter /CCITTFaxEncode /MonoImageDict << /K -1 >> /AllowPSXObjects false /CheckCompliance [ /None ] /PDFX1aCheck false /PDFX3Check false /PDFXCompliantPDFOnly false /PDFXNoTrimBoxError true /PDFXTrimBoxToMediaBoxOffset [ 0.00000 0.00000 0.00000 0.00000 ] /PDFXSetBleedBoxToMediaBox true /PDFXBleedBoxToTrimBoxOffset [ 0.00000 0.00000 0.00000 0.00000 ] /PDFXOutputIntentProfile () /PDFXOutputConditionIdentifier () /PDFXOutputCondition () /PDFXRegistryName () /PDFXTrapped /False /CreateJDFFile false /Description << /ARA <FEFF06270633062A062E062F0645002006470630064700200627064406250639062F0627062F0627062A002006440625064606340627062100200648062B062706260642002000410064006F00620065002000500044004600200645062A064806270641064206290020064406440637062806270639062900200641064A00200627064406450637062706280639002006300627062A0020062F0631062C0627062A002006270644062C0648062F0629002006270644063906270644064A0629061B0020064A06450643064600200641062A062D00200648062B0627062606420020005000440046002006270644064506460634062306290020062806270633062A062E062F062706450020004100630072006F0062006100740020064800410064006F006200650020005200650061006400650072002006250635062F0627063100200035002E0030002006480627064406250635062F062706310627062A0020062706440623062D062F062B002E0635062F0627063100200035002E0030002006480627064406250635062F062706310627062A0020062706440623062D062F062B002E> /BGR <FEFF04180437043f043e043b043704320430043904420435002004420435043704380020043d0430044104420440043e0439043a0438002c00200437043000200434043000200441044a0437043404300432043004420435002000410064006f00620065002000500044004600200434043e043a0443043c0435043d04420438002c0020043c0430043a04410438043c0430043b043d043e0020043f044004380433043e04340435043d04380020043704300020043204380441043e043a043e043a0430044704350441044204320435043d0020043f04350447043004420020043704300020043f044004350434043f0435044704300442043d04300020043f043e04340433043e0442043e0432043a0430002e002000200421044a04370434043004340435043d043804420435002000500044004600200434043e043a0443043c0435043d044204380020043c043e0433043004420020043404300020044104350020043e0442043204300440044f0442002004410020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200441043b0435043404320430044904380020043204350440044104380438002e> /CHS <FEFF4f7f75288fd94e9b8bbe5b9a521b5efa7684002000410064006f006200650020005000440046002065876863900275284e8e9ad88d2891cf76845370524d53705237300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c676562535f00521b5efa768400200050004400460020658768633002> /CHT <FEFF4f7f752890194e9b8a2d7f6e5efa7acb7684002000410064006f006200650020005000440046002065874ef69069752865bc9ad854c18cea76845370524d5370523786557406300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c4f86958b555f5df25efa7acb76840020005000440046002065874ef63002> /CZE <FEFF005400610074006f0020006e006100730074006100760065006e00ed00200070006f0075017e0069006a007400650020006b0020007600790074007600e101590065006e00ed00200064006f006b0075006d0065006e0074016f002000410064006f006200650020005000440046002c0020006b00740065007200e90020007300650020006e0065006a006c00e90070006500200068006f006400ed002000700072006f0020006b00760061006c00690074006e00ed0020007400690073006b00200061002000700072006500700072006500730073002e002000200056007900740076006f01590065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f007400650076015900ed007400200076002000700072006f006700720061006d0065006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076011b006a016100ed00630068002e> /DAN <FEFF004200720075006700200069006e0064007300740069006c006c0069006e006700650072006e0065002000740069006c0020006100740020006f007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400650072002c0020006400650072002000620065006400730074002000650067006e006500720020007300690067002000740069006c002000700072006500700072006500730073002d007500640073006b007200690076006e0069006e00670020006100660020006800f8006a0020006b00760061006c0069007400650074002e0020004400650020006f007000720065007400740065006400650020005000440046002d0064006f006b0075006d0065006e0074006500720020006b0061006e002000e50062006e00650073002000690020004100630072006f00620061007400200065006c006c006500720020004100630072006f006200610074002000520065006100640065007200200035002e00300020006f00670020006e0079006500720065002e> /DEU <FEFF00560065007200770065006e00640065006e0020005300690065002000640069006500730065002000450069006e007300740065006c006c0075006e00670065006e0020007a0075006d002000450072007300740065006c006c0065006e00200076006f006e002000410064006f006200650020005000440046002d0044006f006b0075006d0065006e00740065006e002c00200076006f006e002000640065006e0065006e002000530069006500200068006f006300680077006500720074006900670065002000500072006500700072006500730073002d0044007200750063006b0065002000650072007a0065007500670065006e0020006d00f60063006800740065006e002e002000450072007300740065006c006c007400650020005000440046002d0044006f006b0075006d0065006e007400650020006b00f6006e006e0065006e0020006d006900740020004100630072006f00620061007400200075006e0064002000410064006f00620065002000520065006100640065007200200035002e00300020006f0064006500720020006800f600680065007200200067006500f600660066006e00650074002000770065007200640065006e002e> /ESP <FEFF005500740069006c0069006300650020006500730074006100200063006f006e0066006900670075007200610063006900f3006e0020007000610072006100200063007200650061007200200064006f00630075006d0065006e0074006f00730020005000440046002000640065002000410064006f0062006500200061006400650063007500610064006f00730020007000610072006100200069006d0070007200650073006900f3006e0020007000720065002d0065006400690074006f007200690061006c00200064006500200061006c00740061002000630061006c0069006400610064002e002000530065002000700075006500640065006e00200061006200720069007200200064006f00630075006d0065006e0074006f00730020005000440046002000630072006500610064006f007300200063006f006e0020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e003000200079002000760065007200730069006f006e0065007300200070006f00730074006500720069006f007200650073002e> /ETI <FEFF004b00610073007500740061006700650020006e0065006900640020007300e4007400740065006900640020006b00760061006c006900740065006500740073006500200074007200fc006b006900650065006c007300650020007000720069006e00740069006d0069007300650020006a0061006f006b007300200073006f00620069006c0069006b0065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740069006400650020006c006f006f006d006900730065006b0073002e00200020004c006f006f0064007500640020005000440046002d0064006f006b0075006d0065006e00740065002000730061006100740065002000610076006100640061002000700072006f006700720061006d006d006900640065006700610020004100630072006f0062006100740020006e0069006e0067002000410064006f00620065002000520065006100640065007200200035002e00300020006a00610020007500750065006d006100740065002000760065007200730069006f006f006e00690064006500670061002e000d000a> /FRA <FEFF005500740069006c006900730065007a00200063006500730020006f007000740069006f006e00730020006100660069006e00200064006500200063007200e900650072002000640065007300200064006f00630075006d0065006e00740073002000410064006f00620065002000500044004600200070006f0075007200200075006e00650020007100750061006c0069007400e90020006400270069006d007000720065007300730069006f006e00200070007200e9007000720065007300730065002e0020004c0065007300200064006f00630075006d0065006e00740073002000500044004600200063007200e900e90073002000700065007500760065006e0074002000ea0074007200650020006f007500760065007200740073002000640061006e00730020004100630072006f006200610074002c002000610069006e00730069002000710075002700410064006f00620065002000520065006100640065007200200035002e0030002000650074002000760065007200730069006f006e007300200075006c007400e90072006900650075007200650073002e> /GRE <FEFF03a703c103b703c303b903bc03bf03c003bf03b903ae03c303c403b5002003b103c503c403ad03c2002003c403b903c2002003c103c503b803bc03af03c303b503b903c2002003b303b903b1002003bd03b1002003b403b703bc03b903bf03c503c103b303ae03c303b503c403b5002003ad03b303b303c103b103c603b1002000410064006f006200650020005000440046002003c003bf03c5002003b503af03bd03b103b9002003ba03b103c42019002003b503be03bf03c703ae03bd002003ba03b103c403ac03bb03bb03b703bb03b1002003b303b903b1002003c003c103bf002d03b503ba03c403c503c003c903c403b903ba03ad03c2002003b503c103b303b103c303af03b503c2002003c503c803b703bb03ae03c2002003c003bf03b903cc03c403b703c403b103c2002e0020002003a403b10020005000440046002003ad03b303b303c103b103c603b1002003c003bf03c5002003ad03c703b503c403b5002003b403b703bc03b903bf03c503c103b303ae03c303b503b9002003bc03c003bf03c103bf03cd03bd002003bd03b1002003b103bd03bf03b903c703c403bf03cd03bd002003bc03b5002003c403bf0020004100630072006f006200610074002c002003c403bf002000410064006f00620065002000520065006100640065007200200035002e0030002003ba03b103b9002003bc03b503c403b103b303b503bd03ad03c303c403b503c103b503c2002003b503ba03b403cc03c303b503b903c2002e> /HEB <FEFF05D405E905EA05DE05E905D5002005D105D405D205D305E805D505EA002005D005DC05D4002005DB05D305D9002005DC05D905E605D505E8002005DE05E105DE05DB05D9002000410064006F006200650020005000440046002005D405DE05D505EA05D005DE05D905DD002005DC05D405D305E405E105EA002005E705D305DD002D05D305E405D505E1002005D005D905DB05D505EA05D905EA002E002005DE05E105DE05DB05D90020005000440046002005E905E005D505E605E805D5002005E005D905EA05E005D905DD002005DC05E405EA05D905D705D4002005D105D005DE05E605E205D505EA0020004100630072006F006200610074002005D5002D00410064006F00620065002000520065006100640065007200200035002E0030002005D505D205E805E105D005D505EA002005DE05EA05E705D305DE05D505EA002005D905D505EA05E8002E05D005DE05D905DD002005DC002D005000440046002F0058002D0033002C002005E205D905D905E005D5002005D105DE05D305E805D905DA002005DC05DE05E905EA05DE05E9002005E905DC0020004100630072006F006200610074002E002005DE05E105DE05DB05D90020005000440046002005E905E005D505E605E805D5002005E005D905EA05E005D905DD002005DC05E405EA05D905D705D4002005D105D005DE05E605E205D505EA0020004100630072006F006200610074002005D5002D00410064006F00620065002000520065006100640065007200200035002E0030002005D505D205E805E105D005D505EA002005DE05EA05E705D305DE05D505EA002005D905D505EA05E8002E> /HRV (Za stvaranje Adobe PDF dokumenata najpogodnijih za visokokvalitetni ispis prije tiskanja koristite ove postavke. Stvoreni PDF dokumenti mogu se otvoriti Acrobat i Adobe Reader 5.0 i kasnijim verzijama.) /HUN <FEFF004b0069007600e1006c00f30020006d0069006e0151007300e9006701710020006e0079006f006d00640061006900200065006c0151006b00e90073007a00ed007401510020006e0079006f006d00740061007400e100730068006f007a0020006c006500670069006e006b00e1006200620020006d0065006700660065006c0065006c0151002000410064006f00620065002000500044004600200064006f006b0075006d0065006e00740075006d006f006b0061007400200065007a0065006b006b0065006c0020006100200062006500e1006c006c00ed007400e10073006f006b006b0061006c0020006b00e90073007a00ed0074006800650074002e0020002000410020006c00e90074007200650068006f007a006f00740074002000500044004600200064006f006b0075006d0065006e00740075006d006f006b00200061007a0020004100630072006f006200610074002000e9007300200061007a002000410064006f00620065002000520065006100640065007200200035002e0030002c0020007600610067007900200061007a002000610074007400f3006c0020006b00e9007301510062006200690020007600650072007a006900f3006b006b0061006c0020006e00790069007400680061007400f3006b0020006d00650067002e> /ITA <FEFF005500740069006c0069007a007a006100720065002000710075006500730074006500200069006d0070006f007300740061007a0069006f006e00690020007000650072002000630072006500610072006500200064006f00630075006d0065006e00740069002000410064006f00620065002000500044004600200070006900f900200061006400610074007400690020006100200075006e00610020007000720065007300740061006d0070006100200064006900200061006c007400610020007100750061006c0069007400e0002e0020004900200064006f00630075006d0065006e007400690020005000440046002000630072006500610074006900200070006f00730073006f006e006f0020006500730073006500720065002000610070006500720074006900200063006f006e0020004100630072006f00620061007400200065002000410064006f00620065002000520065006100640065007200200035002e003000200065002000760065007200730069006f006e006900200073007500630063006500730073006900760065002e> /JPN <FEFF9ad854c18cea306a30d730ea30d730ec30b951fa529b7528002000410064006f0062006500200050004400460020658766f8306e4f5c6210306b4f7f75283057307e305930023053306e8a2d5b9a30674f5c62103055308c305f0020005000440046002030d530a130a430eb306f3001004100630072006f0062006100740020304a30883073002000410064006f00620065002000520065006100640065007200200035002e003000204ee5964d3067958b304f30533068304c3067304d307e305930023053306e8a2d5b9a306b306f30d530a930f330c8306e57cb30818fbc307f304c5fc59808306730593002> /KOR <FEFFc7740020c124c815c7440020c0acc6a9d558c5ec0020ace0d488c9c80020c2dcd5d80020c778c1c4c5d00020ac00c7a50020c801d569d55c002000410064006f0062006500200050004400460020bb38c11cb97c0020c791c131d569b2c8b2e4002e0020c774b807ac8c0020c791c131b41c00200050004400460020bb38c11cb2940020004100630072006f0062006100740020bc0f002000410064006f00620065002000520065006100640065007200200035002e00300020c774c0c1c5d0c11c0020c5f40020c2180020c788c2b5b2c8b2e4002e> /LTH <FEFF004e006100750064006f006b0069007400650020016100690075006f007300200070006100720061006d006500740072007500730020006e006f0072011700640061006d00690020006b0075007200740069002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b00750072006900650020006c0061006200690061007500730069006100690020007000720069007400610069006b007900740069002000610075006b01610074006f00730020006b006f006b007900620117007300200070006100720065006e006700740069006e00690061006d00200073007000610075007300640069006e0069006d00750069002e0020002000530075006b0075007200740069002000500044004600200064006f006b0075006d0065006e007400610069002000670061006c006900200062016b007400690020006100740069006400610072006f006d00690020004100630072006f006200610074002000690072002000410064006f00620065002000520065006100640065007200200035002e0030002000610072002000760117006c00650073006e0117006d00690073002000760065007200730069006a006f006d00690073002e> /LVI <FEFF0049007a006d0061006e0074006f006a00690065007400200161006f00730020006900650073007400610074012b006a0075006d00750073002c0020006c0061006900200076006500690064006f00740075002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006100730020006900720020012b00700061016100690020007000690065006d01130072006f00740069002000610075006700730074006100730020006b00760061006c0069007401010074006500730020007000690072006d007300690065007300700069006501610061006e006100730020006400720075006b00610069002e00200049007a0076006500690064006f006a006900650074002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006f002000760061007200200061007400760113007200740020006100720020004100630072006f00620061007400200075006e002000410064006f00620065002000520065006100640065007200200035002e0030002c0020006b0101002000610072012b00200074006f0020006a00610075006e0101006b0101006d002000760065007200730069006a0101006d002e> /NLD (Gebruik deze instellingen om Adobe PDF-documenten te maken die zijn geoptimaliseerd voor prepress-afdrukken van hoge kwaliteit. De gemaakte PDF-documenten kunnen worden geopend met Acrobat en Adobe Reader 5.0 en hoger.) /NOR <FEFF004200720075006b00200064006900730073006500200069006e006e007300740069006c006c0069006e00670065006e0065002000740069006c002000e50020006f0070007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740065007200200073006f006d00200065007200200062006500730074002000650067006e0065007400200066006f00720020006600f80072007400720079006b006b0073007500740073006b00720069006600740020006100760020006800f800790020006b00760061006c0069007400650074002e0020005000440046002d0064006f006b0075006d0065006e00740065006e00650020006b0061006e002000e50070006e00650073002000690020004100630072006f00620061007400200065006c006c00650072002000410064006f00620065002000520065006100640065007200200035002e003000200065006c006c00650072002000730065006e006500720065002e> /POL <FEFF0055007300740061007700690065006e0069006100200064006f002000740077006f0072007a0065006e0069006100200064006f006b0075006d0065006e007400f300770020005000440046002000700072007a0065007a006e00610063007a006f006e00790063006800200064006f002000770079006400720075006b00f30077002000770020007700790073006f006b00690065006a0020006a0061006b006f015b00630069002e002000200044006f006b0075006d0065006e0074007900200050004400460020006d006f017c006e00610020006f007400770069006500720061010700200077002000700072006f006700720061006d006900650020004100630072006f00620061007400200069002000410064006f00620065002000520065006100640065007200200035002e0030002000690020006e006f00770073007a0079006d002e> /PTB <FEFF005500740069006c0069007a006500200065007300730061007300200063006f006e00660069006700750072006100e700f50065007300200064006500200066006f0072006d00610020006100200063007200690061007200200064006f00630075006d0065006e0074006f0073002000410064006f0062006500200050004400460020006d00610069007300200061006400650071007500610064006f00730020007000610072006100200070007200e9002d0069006d0070007200650073007300f50065007300200064006500200061006c007400610020007100750061006c00690064006100640065002e0020004f007300200064006f00630075006d0065006e0074006f00730020005000440046002000630072006900610064006f007300200070006f00640065006d0020007300650072002000610062006500720074006f007300200063006f006d0020006f0020004100630072006f006200610074002000650020006f002000410064006f00620065002000520065006100640065007200200035002e0030002000650020007600650072007300f50065007300200070006f00730074006500720069006f007200650073002e> /RUM <FEFF005500740069006c0069007a00610163006900200061006300650073007400650020007300650074010300720069002000700065006e007400720075002000610020006300720065006100200064006f00630075006d0065006e00740065002000410064006f006200650020005000440046002000610064006500630076006100740065002000700065006e0074007200750020007400690070010300720069007200650061002000700072006500700072006500730073002000640065002000630061006c006900740061007400650020007300750070006500720069006f006100720103002e002000200044006f00630075006d0065006e00740065006c00650020005000440046002000630072006500610074006500200070006f00740020006600690020006400650073006300680069007300650020006300750020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e00300020015f00690020007600650072007300690075006e0069006c006500200075006c0074006500720069006f006100720065002e> /RUS <FEFF04180441043f043e043b044c04370443043904420435002004340430043d043d044b04350020043d0430044104420440043e0439043a043800200434043b044f00200441043e043704340430043d0438044f00200434043e043a0443043c0435043d0442043e0432002000410064006f006200650020005000440046002c0020043c0430043a04410438043c0430043b044c043d043e0020043f043e04340445043e0434044f04490438044500200434043b044f00200432044b0441043e043a043e043a0430044704350441044204320435043d043d043e0433043e00200434043e043f0435044704300442043d043e0433043e00200432044b0432043e04340430002e002000200421043e043704340430043d043d044b04350020005000440046002d0434043e043a0443043c0435043d0442044b0020043c043e0436043d043e0020043e0442043a0440044b043204300442044c002004410020043f043e043c043e0449044c044e0020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200431043e043b043504350020043f043e04370434043d043804450020043204350440044104380439002e> /SKY <FEFF0054006900650074006f0020006e006100730074006100760065006e0069006100200070006f0075017e0069007400650020006e00610020007600790074007600e100720061006e0069006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002c0020006b0074006f007200e90020007300610020006e0061006a006c0065007001610069006500200068006f0064006900610020006e00610020006b00760061006c00690074006e00fa00200074006c0061010d00200061002000700072006500700072006500730073002e00200056007900740076006f00720065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f00740076006f00720069016500200076002000700072006f006700720061006d006f006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076016100ed00630068002e> /SLV <FEFF005400650020006e006100730074006100760069007400760065002000750070006f0072006100620069007400650020007a00610020007500730074007600610072006a0061006e006a006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002c0020006b006900200073006f0020006e0061006a007000720069006d00650072006e0065006a016100690020007a00610020006b0061006b006f0076006f00730074006e006f0020007400690073006b0061006e006a00650020007300200070007200690070007200610076006f0020006e00610020007400690073006b002e00200020005500730074007600610072006a0065006e006500200064006f006b0075006d0065006e0074006500200050004400460020006a00650020006d006f0067006f010d00650020006f0064007000720065007400690020007a0020004100630072006f00620061007400200069006e002000410064006f00620065002000520065006100640065007200200035002e003000200069006e0020006e006f00760065006a01610069006d002e> /SUO <FEFF004b00e40079007400e40020006e00e40069007400e4002000610073006500740075006b007300690061002c0020006b0075006e0020006c0075006f00740020006c00e400680069006e006e00e4002000760061006100740069007600610061006e0020007000610069006e006100740075006b00730065006e002000760061006c006d0069007300740065006c00750074007900f6006800f6006e00200073006f00700069007600690061002000410064006f0062006500200050004400460020002d0064006f006b0075006d0065006e007400740065006a0061002e0020004c0075006f0064007500740020005000440046002d0064006f006b0075006d0065006e00740069007400200076006f0069006400610061006e0020006100760061007400610020004100630072006f0062006100740069006c006c00610020006a0061002000410064006f00620065002000520065006100640065007200200035002e0030003a006c006c00610020006a006100200075007500640065006d006d0069006c006c0061002e> /SVE <FEFF0041006e007600e4006e00640020006400650020006800e4007200200069006e0073007400e4006c006c006e0069006e006700610072006e00610020006f006d002000640075002000760069006c006c00200073006b006100700061002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400200073006f006d002000e400720020006c00e4006d0070006c0069006700610020006600f60072002000700072006500700072006500730073002d007500740073006b00720069006600740020006d006500640020006800f600670020006b00760061006c0069007400650074002e002000200053006b006100700061006400650020005000440046002d0064006f006b0075006d0065006e00740020006b0061006e002000f600700070006e00610073002000690020004100630072006f0062006100740020006f00630068002000410064006f00620065002000520065006100640065007200200035002e00300020006f00630068002000730065006e006100720065002e> /TUR <FEFF005900fc006b00730065006b0020006b0061006c006900740065006c0069002000f6006e002000790061007a006401310072006d00610020006200610073006b013100730131006e006100200065006e0020006900790069002000750079006100620069006c006500630065006b002000410064006f006200650020005000440046002000620065006c00670065006c0065007200690020006f006c0075015f007400750072006d0061006b0020006900e70069006e00200062007500200061007900610072006c0061007201310020006b0075006c006c0061006e0131006e002e00200020004f006c0075015f0074007500720075006c0061006e0020005000440046002000620065006c00670065006c0065007200690020004100630072006f006200610074002000760065002000410064006f00620065002000520065006100640065007200200035002e003000200076006500200073006f006e0072006100730131006e00640061006b00690020007300fc007200fc006d006c00650072006c00650020006100e70131006c006100620069006c00690072002e> /UKR <FEFF04120438043a043e0440043804410442043e043204430439044204350020044604560020043f043004400430043c043504420440043800200434043b044f0020044104420432043e04400435043d043d044f00200434043e043a0443043c0435043d044204560432002000410064006f006200650020005000440046002c0020044f043a04560020043d04300439043a04400430044904350020043f045604340445043e0434044f0442044c00200434043b044f0020043204380441043e043a043e044f043a04560441043d043e0433043e0020043f0435044004350434043404400443043a043e0432043e0433043e0020043404400443043a0443002e00200020042104420432043e04400435043d045600200434043e043a0443043c0435043d0442043800200050004400460020043c043e0436043d04300020043204560434043a0440043804420438002004430020004100630072006f006200610074002004420430002000410064006f00620065002000520065006100640065007200200035002e0030002004300431043e0020043f04560437043d04560448043e04570020043204350440044104560457002e> /ENU (Use these settings to create Adobe PDF documents best suited for high-quality prepress printing. Created PDF documents can be opened with Acrobat and Adobe Reader 5.0 and later.) >> /Namespace [ (Adobe) (Common) (1.0) ] /OtherNamespaces [ << /AsReaderSpreads false /CropImagesToFrames true /ErrorControl /WarnAndContinue /FlattenerIgnoreSpreadOverrides false /IncludeGuidesGrids false /IncludeNonPrinting false /IncludeSlug false /Namespace [ (Adobe) (InDesign) (4.0) ] /OmitPlacedBitmaps false /OmitPlacedEPS false /OmitPlacedPDF false /SimulateOverprint /Legacy >> << /AddBleedMarks false /AddColorBars false /AddCropMarks false /AddPageInfo false /AddRegMarks false /ConvertColors /ConvertToCMYK /DestinationProfileName () /DestinationProfileSelector /DocumentCMYK /Downsample16BitImages true /FlattenerPreset << /PresetSelector /MediumResolution >> /FormElements false /GenerateStructure false /IncludeBookmarks false /IncludeHyperlinks false /IncludeInteractive false /IncludeLayers false /IncludeProfiles false /MultimediaHandling /UseObjectSettings /Namespace [ (Adobe) (CreativeSuite) (2.0) ] /PDFXOutputIntentProfileSelector /DocumentCMYK /PreserveEditing true /UntaggedCMYKHandling /LeaveUntagged /UntaggedRGBHandling /UseDocumentProfile /UseDocumentBleed false >> ] >> setdistillerparams << /HWResolution [2400 2400] /PageSize [612.000 792.000] >> setpagedevice
id	nasplib_isofts_kiev_ua-123456789-83003
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn	0130-5395
language	Russian
last_indexed	2025-12-07T19:06:32Z
publishDate	2011
publisher	Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
record_format	dspace
spelling	Семотюк, М.В. 2015-06-12T14:47:27Z 2015-06-12T14:47:27Z 2011 О существовании точного метода факторизации составных чисел / М.В. Семотюк // Управляющие системы и машины. — 2011. — № 6. — С. 3-9. — Бібліогр.: 7 назв. — рос. 0130-5395 https://nasplib.isofts.kiev.ua/handle/123456789/83003 512(075) Предложен метод факторизации составных чисел по принципу цифра за цифрой, позволяющий за конечное число шагов найти сомножители благодаря теоретико-числовым представлениям систем счисления. Метод позволяет решать диофантовы уравнения, а также получать точный тест простоты чисел. A method of the factoring of the composite numbers is suggested on the basis of digit by digit that makes it possible, by the finite number of steps to find the factors due to the number-theoretic concepts of the number systems. The method allows to solve Diophantine equations, as well as to get an accurate test for primality. Запропоновано метод факторизації складених чисел за принципом цифра за цифрою, що дозволяє за скінченне число кроків знайти співмножники завдяки теоретико-числовому представленню систем числення. Метод дозволяє розв’язувати діофантові рівняння та одержувати точний тест простоти чисел. ru Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України Управляющие системы и машины Фундаментальные и прикладные проблемы Computer Science О существовании точного метода факторизации составных чисел About the Existence of the Accurate Method of the Factoring of Composite Numbers Про існування точного методу факторизації складених чисел Article published earlier
spellingShingle	О существовании точного метода факторизации составных чисел Семотюк, М.В. Фундаментальные и прикладные проблемы Computer Science
title	О существовании точного метода факторизации составных чисел
title_alt	About the Existence of the Accurate Method of the Factoring of Composite Numbers Про існування точного методу факторизації складених чисел
title_full	О существовании точного метода факторизации составных чисел
title_fullStr	О существовании точного метода факторизации составных чисел
title_full_unstemmed	О существовании точного метода факторизации составных чисел
title_short	О существовании точного метода факторизации составных чисел
title_sort	о существовании точного метода факторизации составных чисел
topic	Фундаментальные и прикладные проблемы Computer Science
topic_facet	Фундаментальные и прикладные проблемы Computer Science
url	https://nasplib.isofts.kiev.ua/handle/123456789/83003
work_keys_str_mv	AT semotûkmv osuŝestvovaniitočnogometodafaktorizaciisostavnyhčisel AT semotûkmv abouttheexistenceoftheaccuratemethodofthefactoringofcompositenumbers AT semotûkmv proísnuvannâtočnogometodufaktorizacíískladenihčisel

О существовании точного метода факторизации составных чисел

Institution

Ähnliche Einträge