Nabla-deltorial-contrary (N-D-C)
— is a method of “reverse” factorization, and
was created as the fourth stage of attempts, each of which, although not
entirely successful, was a step forward.
In each of these
methods, the most important thing was to find the best way to select a few
(used in subsequent steps) “working” primes: their products obtained in this
way were to be the test numbers p₀; p₁; p₂; p₃...
pₙ — with which subsequent attempts were made to factor the tested number
𝒂.
Since the
selection of these factors is crucial, it will be discussed in the most detail.
In the first step, we tried to use the function 𝒑𝒓𝒊𝒎𝒐𝒓𝒊𝒂𝒍, but
the numbers it generated grew so quickly that they turned out to be useless.
The Van(guard) function was supposed to solve this problem by defining the
quantity #p₁ (note the new designation of the newly introduced function,
different from 𝒑𝒓𝒊𝒎𝒐𝒓𝒊𝒂𝒍,
because the # sign, the operator sign — precedes the number it affects!) — such
that
#p₁ =
p₁# : p₀#
but its
performance, although it partially met expectations, was insufficient: the
resulting numbers were still much too large!
Therefore, in
the next, third step, we decided to tame them using the nabla-deltorial
(nDeltorial) function, i.e. a method of their
specific shuffling, and building an alternating product: the smallest times the
largest, then times the second, then times the penultimate, times the third,
with the third from the end - and so on, and so on... Of course, if we are
talking about "the end", it means that the numbers used are from a
certain closed range, defined by us - this is probably understandable...
This was already
a quite good method, but it was completely unsuitable for cryptographic keys,
because it would then mean the need to use test numbers consisting of only two
components (the product of two large prime numbers), and this would mean that
the profit from using the given method would be doubtful (to put it mildly).
And at this
point, the epiphany occurred! But to explain the matter, it requires some
introduction: the basic way of trying to factor the tested numbers is to divide
them by an appropriately selected test number, and this is a kind of canon.
Therefore, consistently following this approach, we had to reach the place
where we found ourselves, i.e. the wall. A completely new approach was needed
and it turned out that it is possible: instead of dividing the number being
tested by the number being tested, we should do the opposite! That is, divide
the appropriately selected test number p₀ by the number being tested 𝒂, and
as a result we will get a certain remainder 𝒓,
which carries information about what we need for happiness!
Where does this
change come from that is revolutionary? Well, until now we would have been
condemned to limit the size of the test numbers, because if we are to divide 𝒂 by
the product of primes, then it is clear that it must be smaller than 𝒂! Now
there is no such restriction, and thanks to this, the selected pₙ can be
the product of a really large portion of prime numbers, and we will check with
ONE division whether 𝒂 is divisible by
any of them...
__
Our basic
equation then looks like this:
p₀ = 𝒃 • 𝒂 + 𝒓
where p₀
is the test number, 𝒂 is the number we need to factor,
𝒃 is
the multiplier calculated in a simple way, and 𝒓 <
𝒂 —
the remainder of the division. Now, if there is some number (and if there is
ANY, then there is also a prime number) that divides the right side of the
equation, then it also divides its left side, this is obvious. We know
perfectly well what prime numbers divide the left side, because we
"constructed" this number ourselves. If now one of its divisors also
divides the number 𝒓 — but does not divide the number
𝒃,
then it MUST divide 𝒂 — and there is no mercy, that
is, no forgiveness, as we say in such situations in Poland...
It should also
be noted that we are operating with divisors built of several hundred digits,
while the number 𝒃 will be built of only a few
digits, sometimes three, sometimes nine, sometimes even several dozen — but
therefore it will not interfere with us here in any way... STOP! Error: we must
choose the test numbers p₀ — pₙ so that 𝒃 is
large: large, but not TOO large: smaller in terms of length expressed in the
number of digits, than the smallest component of the test number (p₀ —
pₙ). I will skip the explanation: those who are smart — will
understand...
Note that the
decomposition of 𝒓 will usually (but not always!)
be much (or even many times) easier than the decomposition of 𝒂, for
several reasons:
1. Most often, 𝒓 will
be much smaller than 𝒂, and then the
decomposition is ALWAYS easier.
2. In fact, the
only situations we are interested in are those in which 𝒓 is
divisible by one of the terms of p₀, and this will be quite easy to
check!
— but wait!
(someone will exclaim) that means that it will have to be divided SEQUENTIALLY
by ALL the terms of p₀—and if so, there is no gain in computational
complexity, not the slightest, quite the opposite!
Well, no: such a
necessity will not arise very often. For example, in about 50 percent of the
cases it will be the case that 𝒓 will be smaller
(often much smaller) than most of the terms of p₀—and sometimes even ALL
of them! And if so, p₀ is "checked off" — and we get to
p₁ after performing ONE (sometimes several, in fact), SIMPLE comparison
(subtraction) operation...
3. The number 𝒂
being tested is specially chosen to be difficult to factor, but that's not the
case for 𝒓!
Most often, it will be a product of primes such that some of them won't be very
large, which will make factoring easier — and you don't need much luck for
that. And if we're VERY lucky — it will also be a product containing one of the
components of 𝒂.
ONE - so finding
it will be a trivially simple task, because it is enough to divide 𝒓 by
all those small prime numbers that make up the number 𝒓, and
which we can find quite easily (rather using classical methods), because as
indicated: quite often they will not be very large, and if we start with the
smallest ones, then it will be "downhill" from there...
Calculating the
second component of 𝒂 simply consists of dividing by
the found component, which even a more intelligent child can handle, and
without using a calculator...
Someone may have
missed an important element in these considerations, namely, what is the
advantage of using the "inverse" method? It results from the fact
that thanks to it we can choose very, very large test numbers! Thanks to it,
they will be the product of MANY prime numbers, carefully selected for this
purpose.
Time for a short
summary:
We take the test
number 𝒂 and
extract the square root of it. Then we find the closest number divisible by 6:
all prime numbers are neighbors of such a number. Now the task branches into
two tracks:
1. Numbers
smaller than it
2. and larger.
In the first
case, we will consistently move down, taking smaller and smaller numbers, while
in the second case we will move up, taking larger and larger numbers.
Case 1:
From the number
found (divisible by 6), we subtract one and check whether it is a prime number.
Then we will take the next numbers, moving between them with a chess knight's
move: 4; 2; 4; 2; 4; 2... (because prime numbers appear in such distance
intervals Δ)
Here is a small
digression, level’ (1):
- we do not
perform certain actions, such as the above "check" - in real time and
do not burden the running algorithm with great effort, but we have to do it in
advance, and we have to have the prime numbers (from the ranges we are
interested in. All. ALL!) already compiled and numbered in advance.
Digression,
level" (2):
Tabulating
hundreds of thousands of billions of numbers, each consisting of several
hundred digits - would take up a lot of memory, so to save it, you can use a
trick, namely NOT to save them 𝑖𝑛 𝑒𝑥𝑡𝑒𝑛𝑠𝑜, but
in vector form, i.e. saved "with all digits" only every 65,536
positions, and every 256 - with partial expansion (the last places after the
decimal point, closing the given number. Or as Δ, i.e. the distance from
the leading position), and then on 255 fields only Δ, i.e. how far the
given number is from the number indicated (partially!) in the first position of
the given "file". However, since the use of this database will have
its own requirements, to "read" it you will need a specialized
algorithm that will quickly change the numbers saved in the form vector, to the
forms represented by 𝑖𝑛 𝑒𝑥𝑡𝑒𝑛𝑠𝑜.
[digression
level" off, digression level' — off]
So the program
working in real time will only send a question to our prime number store: does
the number being sent have its shelf there?
And after some
time (because it is rather rare the first time) — the answer will be
"yes" — so from now on all subsequent numbers from a given shelf in
our prime number store will be used for the further algorithm. As you can see,
creating such a store is a key issue and will determine the capabilities of its
owner.
Since there is
no point in shooting a sparrow with a cannon, we will initially assume with not
too much momentum how big the test number p₀ should be — which will also
determine how many NEXT prime numbers we want to take from the store, and I
remind you that we will run both "lower" and "higher"
numbers at the same time. From the received numbers we create the next nDeltorials, i.e. p₀; p₁; p₂; p₃ — all
the way to pₙ — because it is clear that it
will not end with one attempt!
To further
illustrate the principle of creating nDeltorials — we
will use a certain metaphor:
Let's imagine a 𝒏-story
skyscraper (and we do not know how big 𝒏
is!), which will symbolize the principle of our action. A number divisible by
6, reduced by 1, (the number closest to the square root of 𝒂) —
constitutes the "base" floor — i.e. the starting point. Starting from
it — one brigade moves down, and the other up. The numbers defining the number
of the floor on which these two brigades are simultaneously — after adding up
are always constant, equal to 2𝒏 — because when
one brigade goes down, the other at the same time goes up by the same number of
floors. Each nDyltorial is created from such a
selected product, i.e. where p₀ has a "ceiling", p₁ has a
"floor". And where p₂ has a "ceiling" - there is a
"floor" p₃ - and so on, and so on, and so on...
Let me remind
you of the fact on which the advantage of the method proposed here is based,
that multiplication is faster than division, and the difference is several
dozen percent. So instead of dividing the test number by all the test numbers
in turn, we create the product of these test numbers. The second 𝑛𝑜𝑣𝑢𝑚 is
that instead of dividing 𝒂 by p₀ -
we divide the created product by 𝒂, and then
factorize the resulting 𝒓, which should
(should! Well, but USUALLY - will be) be much easier...
That's all.
𝑁𝑖𝑐𝑜𝑙𝑎𝑠 𝑅𝑎𝐵𝑎𝑟𝑏𝑎𝑟(𝑠)𝑘𝑖
‘shrink’
(shortened link) to the above:
Previous approaches to the
problem: tinyurl.com/PrimorialRiddle
.