Moaña and the crab

MAIN PAGE

Moaña and the Crab.

An informal essay on machines performing arithmetic and subarithmetic
operations with special attention to the factoring problem.

by

Jacques BASALDÚA

                                                                                        C O N T E N T S

    2. A quick look at a multiplication machine
        2.1 Dividing the machine in two different parts
        2.2 Properties of the extended product
        2.3 Reversing multiplication

    3. Introducing RL division
        3.1 a mod b = 0 <-> a RLmod b = 0 <-> a div b = a RLdiv b
        3.2 An application of RL division: Computing square roots

    4. Moaña formulae: Factoring analytically
        4.1 Formalization
        4.2 A syntactic approach: The parser
        4.3 A semantic approach: The profiler
        4.4 A probabilistic approach: Independence
        4.5 A quantum approach: A letter to Santa Claus

    5. The CRAB (Crawling Reversible Automat Body)
        5.1 Three aspects of the same problem
        5.2 Reversibility of the algorithm
        5.3 Operation with periodic forms
        5.4 Vertical analysis of the periodic form
        5.5 Horizontal analysis of the periodic form
        5.6 Antisymmetry
        5.7 Final carrying
        5.8 General form of ß(n)

Jacques Basaldúa (c) 2001
All Rights Reserved

This article may be reproduced unmodified either in printed or online journals or websites, except
in websites who charge downloading fees or otherwise limit free and universal access to scientific material.
Printed media may only charge their regular fees.

Please, append the URL www.dybot.com/numbers/crab.htm to any reference to it.

Depósito Legal GC-6519/01
Este artículo fue registrado en el Registro de la Propiedad Intelectual de Las Palmas de Gran Canaria, España, el 14 de diciembre de 2001.

1. Introduction: What is this?

    Unlike its co-article www.dybot.com/numbers/sqfree.htm, which is a formal and self-contained exposition about some consequences of the properties of ß(n), this article should be regarded as a journey through different aspects of the factoring problem trying to understand why and when it is intrinsically "heavy". Before starting this article, at least points 1, 2 and 5 of the mentioned article should be read.

    Before we start deconstructing the multiplication machine, let's introduce a child level example to have a first contact with the factoring problem. Factoring a given composed integer M is finding two integers p and q such that p·q = M, p=/=1 and q=/=1. A complete factorization is repeating the process to all composed factors obtained, until we get a set of prime numbers (p, q, r, s ...) whose product is M. This set is called the prime decomposition of M.

    Imagine a newcomer with school level mathematical knowledge facing the problem for the first time of his life. He has to find an efficient method to factor a number M. He has been told about verifying divisibility of M one by one by all prime numbers smaller than the square root of M. He thinks this is way too slow, he has to find something much better.

    He reasons:            M = Q² + R (where Q is Ö M and R is some remainder. If R is 0, it's finished. )
    Can be written as   M = (Q - i)(Q + i) + R + i²     He pretends to find some value i satisfying Q - i divides M. From the expression, he observes that it must also divide R + i².
    In current language we would say: R + i² is congruent with M modulo Q - i. Because (Q - i)(Q + i) is obviously a multiple of Q - i.

    So he is looking for an integer n satisfying n = (R + i²)/(Q - i), he applies school level math and gets:

            i = (-n ± Ö (n² + 4nQ - 4R))/2

    And the problem now is finding the n that makes n² + 4nQ - 4R a perfect square.

    He reasons: "Maybe starting otherwise, I can get rid of the 4nQ term, getting something as n² + a constant."

    After some trial, he gets -M = Q(-Q) + R (After all, factoring -M is as good as factoring M.)
    can be written as: - M = (Q - i)(i - Q) + R - 2Qi + i²    producing n = (R - 2Qi + i²)/(Q - i)
    and i = (2Q - n ± Ö(n² + 4Q² - 4R))/2

    Now he has n² + 4Q² - 4R which is "n² + a constant" as a perfect square. He reasons: "4Q² - 4R is the difference between two squares."

    After some thinking "à la grecque" (the ancient greek style),

***· ***·· ***··· ***···· ***· ***·· ***··· ***···· ***· ***·· ***··· ***···· ···· ····· ······ ······· ····· ······ ······· ······ ······· ·······
    he concludes that "the difference between two squares is the sum of consecutive odd numbers."

    "Expressing 4Q² - 4R as the sum of consecutive odd numbers is feasible." he thinks. And he is right, because the sum of two consecutive integers 2k+1 and 2k-1 is 4k and the number 4Q² - 4R is also divisible by 4. So he can determine k and then go back to n, i and finally the desired factor Q - i.

    So he did solve a problem that has tortured humanity since Euclid. Or not? What is wrong?

    Only a single word is wrong, the word "feasible". It should be replaced by "trivial". The method works, but it produces the trivial factors 1 and M. Of course, if M is not prime, there is "some other" way to express 4Q² - 4R as the difference of two squares and it is that way which would produce non-trivial factors.

    Besides: a. 4Q² - 4R is just a way of disguising 4M. b. Converting the factoring problem to a square difference problem can be done more elegantly, and that was done by Pierre de Fermat in the XVIIth century. Nevertheless, this is not the point where I pretend to go.

    My point is: No matter how you transform a problem, trivial solutions will always be translated into trivial solutions.

    This could be used as the Principle Zero of Computer Science (PZCS). Don't think I mean this informally, as a new Murphy's law. I mean it in the sense of the Principle Zero of Thermodynamics. (Before the 1st Law of Thermodynamics, which is equivalent to the law of conservation of energy, some authors, for methodological requisites, define a Principle Zero referred to the temperature of isolated systems.) Some readers may not find the relation between the factoring problem and Thermodynamics obvious. Bear in mind that modern (also called statistical) Thermodynamics studies the behavior of particles having two possible states (information bits) and proves that erasing a single bit of information generates at least ln(2)kT Joules of heat. Where k is Boltzman's constant, T is absolute temperature and a Joule is a unit of energy. Computer technology is not yet concerned with this limit, but while miniaturization of circuits goes on, technology will reach the point at which this limit can no longer be ignored. There are many interesting articles available online on this subject. (Search the web for keywords as: Reversible logic, or Toffoli gates).

    Don't expect this article to be an exposition of some principle of conservation of energy applied to solving problems using computers. This is way beyond the aspirations and skills of the author. What it does point is that we lack of such a principle, which would definitely solve the P vs NP problem. NP is the common way to name problems being very hard to solve (the time requested increases more than polynomially with input size) but for which verifying the accuracy of a given solution is easy. P (for polynomial time) are considered "easy" problems. The P vs NP question is whether P and NP are different, or NP belongs to P. It is an open question in Computer Science. The most studied of all NP problems is the factoring problem. For more complicated problems, Computer Science studies the limits of computability in terms of the halting condition of a Turing machine. The machines studied in this article are so simple that studying their halting problem is uninteresting, but they still do factoring.

    In this article, we will see the factoring problem studied syntactically, semantically, probabilistically and will always have to deal with the inherent complication of the factoring problem repeatedly. We will see an exception to this "pessimistic" reality when analyzing the problem using a quantum machine. This is because the analysis is much more a letter to Santa Claus than the real analysis of a real machine. This article argues that if an n-qbit wide arithmetic unit can be built and that unit is capable of inverting ANDed terms plus one other boolean operation (as the OR operation), factoring n-bit-long numbers can be done in P using such a machine. Obviously, for small values of n, a "brute force" attack using a conventional computer is as good, but ... Will quantum computers of more than a few qbits ever exist? Or, why should quantum physics be an exception to "that not existing conservation law we lack of", if it is not an exception to the first Law of Thermodynamics?

to the top

2. A quick look at a multiplication machine

Let's study the following machine:

    The blue vertical lines represent the bits being ON (1) of some register containing a number, called q in the following, which is on top of the machine. In the picture the rightmost bit is the least significant bit, namely q_o. The yellow horizontal lines represent the 1s of an other register containing an other number called d which is in the right part of the machine with its least significant bit d_o at the bottom part of the register. The crossing points of any two lines are indicated by white dots. These white dots slide along the diagonal cyan lines an "fall" to the bottom of the grid where they are stacked in an abacus-like structure. The grid's only function is to make counting easy. This "abacus" can also be considered a register e containing a number but, unlike the registers q and d, it is not made of simple bits, but of integer values 0, 1, 2, 3, ...

    Each bit number n of e is: e_n= S(i=0,n) of d_i·q_n-i where the symbol · is the boolean AND operation of two bits of d and q.

    If q is the arithmetic value contained in the register q = q_k-12^k-1 + . . . + q₂2² + q₁2¹ + q_o2⁰, d is similarly d = d_k-12^k-1 + . . . + d₂2² + d₁2¹ + d_o2⁰and e = e_2k-12^2k-1+ . . . + e₂2² + e₁2¹ + e_o2⁰.
    k is the number of bits of the factors, 2k is the number of bits of the result.

    It can easily be verified that e satisfies e = dq (I don't use any sign for multiplication in points 2 to 4, because I use a notation for boolean expressions. · is AND and × is XOR, + will no longer mean addition in the arithmetic sense, ± will be used instead.)

    Because e is the product of d times q (but considering it is not a simple binary register containing 0s and 1s but a register containing integer values), we will call e the extended product of d times q.

    Below, just at the bottom of the machine we can see an ordinary binary register, which we will call fp (forward product). Note that since we pretend to do "backwards multiplication" we reserve the name m (module) for the result we pretend to get.

    Converting e to fp can also be done in boolean notation (see point 4.1) but, for the moment, we will give a pseudocode algorithm:

    let c=0                        // A carry register
    for i=0 to 2k-1 do begin       // All bits starting with the least sig. The result has 2k bits.
       if e_i+c is odd -> fp_i is 1
       else           -> fp_i is 0
       let c = »(e_i+c)             // » means shift 1 bit to the right. (Unsigned div by 2)
    end

This algorithm is also the heart of the Crab, a circuit that computes the modular inverse of a number modulo 2^¥, which will be studied in chapter 5.

to the top

2.1 Dividing the machine in two different parts

    From the previous analysis, it follows that the multiplication machine has two different parts which we will call, somewhat informally, the logic part of the machine, namely computing the extended product from the factors, and the arithmetic part of the machine, namely computing the binary product from the extended product.

    The two parts are referred to as subarithmetic machines since they perform separate parts of an arithmetic operation. The sense of this division will be clearer after seeing curious properties of the extended product and after trying to perform multiplication backwards.

    If you wish to experience with these machines and other related operations such as RL division, ß and more, you may download a simple (Microsoft Windows) interactive program here www.dybot.com/numbers/fac10.zip, but please, don't expect any support concerning the use of the software.

    Summarizing:

The logic part of the multiplication machine is computing e from q and d.

e_n = S (i=0,n) of d_i·q_n-i
_.

The arithmetic part of the multiplication machine is computing fp from e.

    let c=0
    for i=0 to 2k-1 do begin
       if e_i+c is odd -> fp_i is 1
       else           -> fp_i is 0
       let c = »(e_i+c)
    end

to the top

2.2 Properties of the extended product

    Noting these properties of the extended product may give some additional light on the machine.

    2.2.1. The extended product is not commutative.

    Some cases are, particularly the trivial cases where either q or d is 1. But in general it is not.

    2.2.2. If e = extended product(q, d), e ^<- = extended product(q^<- , d^<-) where n^<-is the transposed of n.

    The transposition of a register is done by writing its bits in reverse order. 100111 is the transposed of 111001.

    Consider the extended product without any particular bit being the least or most significant. Ignore the existence of any arithmetic value associated to the bits and you will note that this property is a trivial consequence of the symmetry of the machine.

    2.2.3 The number of bits being one in the product (i.e., S (i=0,2k-1) of e_i) is the product of the number of ones in each factor.

        S(i=0,2k-1) of e _i= (S (i=0,k-1) of q_i)(S (i=0,k-1) of d_i)

    Remember the first description of the machine where the points at the intersection of the lines slide along the diagonals. No points are created or destroyed, so this is also trivial.

to the top

2.3 Reversing multiplication

    The first naïve attempt to factor a number is just writing it in the result register and then "adjusting the bits" to find a pair of valid factors.

    The best way to understand this is: just trying (and obviously failing).

    Computing e backwards from fp is, unfortunately, too easy. First copy fp into e. You get a valid result for a trivial product. E.g. 1 x M, M x 1 and in some cases other trivial products as 101 x 1000001 = 101000101. Here we use the word trivial product when no bit of e is bigger than 1.

    Now take any bit being a 1 and move it to the column immediately to its right. Convert it into 2 bits. This can be repeated as many times as desired. Doing this we get something "looking" like an extended product. Its arithmetic value remains unchanged, since the numbers in one column "are worth" double as the numbers in the column immediately to its right. Note that the number of such "extended product looking" numbers is "astronomically" bigger than M. Since M is of the same magnitude as 2^2k-1 and this number is of the same magnitude as k^2k-1. Of course, not all bits of e can contain values as high as k. The total number of bits must be composed (as mentioned in 2.2.3), and other restrictions surely apply, but this does not change the dreadful situation significantly enough.

    We see the PZCS again, trivial solutions produce trivial solutions. The problem has been transformed into a much bigger problem than it was. We have more choices to consider than in the original problem. Besides, the method to verify if an "extended product looking number" really satisfies a pair of factors is complicated. (Reversing the logic part of the machine is easier than factoring, but far from easy.) This is the essence of an NP problem: having to explore many candidates using a function that verifies their validity but does not give any information on how to improve a candidate.

    What makes a problem hard is having many choices and not having an evaluation function that can be queried about which of two given choices is closer to be a solution. It can also be noticed that the problem can be transformed into a new one with more choices than the original (as in this case) or with less. Simple factoring algorithms as Monte Carlo require ÖÖM steps to complete instead of the original Ö M steps. This seems to point against the idea suggested in the introduction that there is some sort of conservation law that makes a problem inherently difficult, but it only proves that there is no conservation law of the number of choices. Otherwise: no bijective application between the branches to be explored in one form of the problem and the branches in other forms of the same problem. But there seems to be a minimum number of branches to be explored in either form and a common belief that the asymptote is not in P.

    The lack of a function that helps improving the search when evaluating two candidates q and q' is not proved either. It is clear that simple functions like the remainder of the division are meaningless. I.e., concluding that q is a better candidate than q' to be a divisor of m because m mod q < m mod q', is pointless. E.g. m mod 2 is always 1 and the knowledge of that fact does not take us any closer to a solution.

to the top

3. Introducing RL division

In the previous point it was exposed that it is very difficult to find 2 factors satisfying fp (forward product) = M simultaneously. A much easier problem is: for a given factor q, what is the best co-factor d to adjust the multiplication. If q divides M, obviously d must be M div q. If q does not divide M as shown below,

    d = M div q produces an fq whose most significant bits correspond with those of M. (In the example M is 5730875, q is 2381 and d is 2406)

    Division, called here LR division (left to right), is usually considered a simple operation, but analyzing it with boolean equations is far from simple even for small bit sizes. Remember how division was done before using calculators: Every time a new digit of the result has to be estimated, the remainder has to be checked if bigger or equal to the result times that digit. Even if dividing (or any arithmetic op.) is much easier in binary than in decimal, because the only possible new digits of the result are 0 and 1, two numbers have to be compared at each step. Comparing two numbers (which one is smaller) requires: checking 1 bit 50% of the times, 2 bits 25%, 3 bits 12.5%, ... once in a million 20 bits have to be checked (2²⁰= 1024²). This is to say, all bits affect the result at each step and that makes the analysis dreadful. Is there any other way to divide instead of LR division?

    Obviously, RL division. (right to left division):

    As it can be verified from the image: if d = m RLdiv q, q times d matches an arbitrary number of least significant bits of the result (32 in this case).

    How is RL division computed?

    Informally: RL division is the same as multiplication except that instead of computing the result, one of the factors is altered to satisfy a predefined result. Multiplication is not computed entirely at once, but done while the cofactor is being altered.

    Example: Let's see this for 4 bits -> 7 bits: m = 91, q = 13

        The factor is q = (1, 1, 0, 1)
        The cofactor is d = (d6, d5, d4, d3, d2, d1, 1)            (There is no interest to generalize this to even numbers, since removing the prime factors 2 is trivial.)
        The module is m = (1, 0, 1, 1, 0, 1, 1)

        Multiplication starts:

        m0 = q0·d0 = 1 (carrying = 0)

        m1 = q1·d0 ± q0·d1 = 0·1 ± 1·d1 = 1   ->  d1 = 1, carrying = 0

        m2 = q2·d0 ± q1·d1 ± q0·d2 = 1·1 ± 0·1 ± 1·d2 = 0  ->  d2 = 1, carrying = 1
        (Note: d2=0 would make e2 odd and m2 = 1, d2=1 makes e2=2 m2=0 and carries »e2 = »2 = 1)

        m3 = q3·d0 ± q2·d1 ± q1·d2 ± q0·d3 = 1·1 ± 1·1 ± 0·1 ± 1·d3 = 1  ->  d3 = 0, carrying 1
        (Note: e3 = 1 (carried) + 2 + 0, d3=1 would make e3 even -> m3=0, carries »e3 = »3 = 1)

        m4 = q3·d1 ± q2·d2 ± q1·d3 ± q0·d4 = 1·1 ± 1·1 ± 0·0 ± 1·d4 = 1  ->  d4 = 0, carrying 1

        m5 = q3·d2 ± q2·d3 ± q1·d4 ± q0·d5 = 1·1 ± 1·0 ± 0·0 ± 1·d5 = 0  ->  d5 = 0, carrying 1

        m6 = q3·d3 ± q2·d4 ± q1·d5 ± q0·d6 = 1·0 ± 1·0 ± 0·0 ± 1·d6 = 1  ->  d6 = 0, carrying 0

RL division makes part of Moaña expressions, and it will be formalized later (see 4.1)

a RLdiv b computed up to k bits = the product of a times the modular inverse of b modulo 2^k.

    This follows of:

        a RLdiv b = a(1 RLdiv b)

    and

        b(1 RLdiv b) = xxx0000000000001 (As many zeros to the right as a predefined k.)

    If we compute this up to k bits, b(1 RLdiv b) is congruent with 1 (modulo 2^k). This is the definition of modular inverse of b modulo 2^k.

1 RLdiv b is the modular inverse of b modulo 2^k.

    For the particular case k = ¥ , 1 RLdiv b is called the periodic form (PF) of b.

    The periodic form of a number n, PF(n) is a number created by the infinite repetition of a constant pattern, satisfying:

      a. n times PF(n) = xxx000...0001 (An infinite number of zeros before the 1)
      b. Although arithmetically n times PF(n) = ¥ , (n times PF(n)) mod 2^¥ = 1

PF(n) = 1 RLdiv n computed for an ¥ number of bits.

The period (length of the repeated pattern) of the periodic form of an odd number n is ß(n). Which, until now, we had defined as "the order of the subgroup of the powers of 2 modulo n".

Chapter 5 is dedicated to the study of periodic forms of numbers and the properties of ß(n), which have many consequences in Number Theory as explained in www.dybot.com/numbers/sqfree.htm.

to the top

3.1 a mod b = 0 <-> a RLmod b = 0 <-> a div b = a RLdiv b

    Before talking about this triple condition, I will explain what is understood by RLmod. Remember the RL division 91 RLdiv 13 shown in the previous point. Since 13 divides 91, the method ends after m6 because carry=0 and all bits of m, q and d higher than 6 were 0. This does not happen when computing m RLdiv q and q does not divide m. In that case, after k bits, even if m and q are 0 for bits higher than k, neither the bits of d, nor the carrying are zero. These bits of d between k and 2k (where k is the number of bits of the factor), are called the RL remainder of m RLdiv q = m RLmod q. The RLmod is k bit long, because it can be easily be proved that: Assuming k is at least the number of bits of q, if and only if those bits are all 0, any bit above will also be 0. Unlike the remainder of the division, which does not depend on any arbitrary k, the remainder of RL division does. Therefore, it does not seem a very interesting characteristic of this operation. Nevertheless, it does play an important role in Moaña formulae (see chapter 4) and what does not depend on k, is whether it is equal to zero or not.

    This triple condition is equivalent to: either b divides a or not.

    If b divides a:

      1. a mod b = 0
      2. a RLmod b = 0
      3. a div b = a RLdiv b

        The third clause seems less obvious than the others, but consider the following:

            b(a div b) has, at least, its most significant bits equal to those of a. If b divides a, b(a div b) = a (all bits).
            b(a RLdiv b) has, at least, its least significant k bits equal to those of a. If b divides a, b(a RLdiv b) = a (all bits).

            If b divides a, b(a div b) = a = b(a RLdiv b)

    If b does not divide a:

      1. a mod b =/= 0
      2. a RLmod b =/= 0
      3. a div b =/= a RLdiv b

to the top

3.2 An application of RL division: Computing square roots

    Although simpler than LR division, at least analyzed using boolean expressions, RL division is neither faster (since computers have integer division implemented in hardware) nor of any practical use, because, when b does not divide a, a RLdiv b is arithmetically meaningless.

    Two uses of RL division may be mentioned:

    a. Serving as a brick to build higher level boolean expressions to analyze arithmetical problems (see Moaña in next point).

    b. Computing square roots. Again microprocessors are not designed to take any advance of the simplicity of this method, so simplicity will not be translated into speed. And again, if the number tested is not a perfect square, the result obtained is a failure status instead of a rounded value which would be more useful.

    An example first: This can be followed using the interactive program mentioned in 2.1. (A file called root.fac contains the starting position.)

    Start with q = 1, m = 88209 (a square number.) We want to compute Ö88209.

      1. The machine on the left (in the software) computes d = m RLdiv q -> d = 88209. The complete calculation is unnecessary, we only need to compute d until the first 1 above d0 (Note that it cannot be d1 -> no square is congruent with 3 modulo 4.) d is 10101100010010001 (the grayed bits should not have been computed) The first 1 in d is d4.

      2. Knowing the index of the first 1 in d, toggle the previous bit of q. q3 = 1 producing: q = 9 and d = 9801. Of course, since we are computing a square root (a number producing itself as a cofactor) the bits below this index do not change. The next 1 bit of d is now d6.

      3. Again, we toggle the previous bit of q. q5=1 producing: q = 41 and d = 2618884649 (for k=32 bits). Ignore the value of d since it only has to be computed until the first 1, d9.

      4. We toggle the previous bit of q. q8=1 producing: q = 297 and d = 297. We reached the square root.

    Let's write this down in pseudocode.

//  0. Prolog to make the algorithm applicable to even numbers
            if m is even -> begin
                let zr = the number of consecutive least significant zeros of m.
                if zr is odd -> return an error // The number is not a square.
                let r = 2^zr/2         // r is stored to multiply the result obtained at the end
                let m = m SHR zr     // shift m zr bits to the right converting it into an odd number
            end

//  1. The main body

            let Q = 1                  // Variable containing the square root while it is computed
            let j = 1                  // Index to the "first candidate" bit
            let f = numBits(M) DIV 2   // Index to the "last candidate" bit.
                |
    +---------->+
    |           |
    |       if j>f -> Halt             // M is not a square
    |           |
    |       [Compute M RLdiv Q from bit j
    |        until a bit being 1 is found.
    |        let k be the index of that bit]
    |           |
    |       if k=f -> goto 2.
    |           |
    |       if k - 1 = j -> Halt       // M is not a square
    |           |
    |       let j = k - 1
    |       let Q = Q + 2j
    |           |
    +-----------+

//  2. The end

            [Compute the remaining bits of M RLdiv Q]
            if any of the bits is non zero -> Halt   // M is not a square
            if some r was defined in step 0 -> let Q = r·Q
            return Q

A fact has to be mentioned: if Q is congruent with 3 modulo 4 (remember M cannot be congruent with 3 modulo 4, but Q can), the method cannot be applied to determine the first bit. This can be verified after the algorithm fails. If the algorithm fails (only the first time) try setting Q as 11 and proceeding with the algorithm normally. I did not reflect this in pseudocode to keep it simple.

to the top

4. Moaña formulae: Factoring analytically

    The previous chapter introduced the following idea:

    m mod q = 0 <-> m RLmod q = 0 <-> m div q = m RLdiv q

    This chapter uses this for factoring using boolean expressions.

    Define m as the module which we pretend to factor. m is replaced by constant values 0 and 1 as required.
    Define fb as the number of bits of the factors. It must be big enough to contain both the factor and its cofactor, but not to contain m.
    Define q as the non-trivial factor we pretend to find. q is replaced by the boolean variable values q_fb-1, ... q₃, q₂, q₁, 1.

    Compute d = m RLdiv q the bits of d are boolean functions of q_fb-1, ... q₃, q₂, q₁.

    The condition q divides m is, as mentioned, equivalent to m RLmod q = 0, therefore:

    Define Mo(m) = !d_2fb-1·!d_2fb-2· ... ·!d_fb+1·!d_fb (! is NOT, · is AND)

    Mo (for Moaña) is the function that makes all the bits of d from fb to 2fb-1 equal to zero. It has been mentioned that these bits are the remainder of the RL division and that the condition that makes this remainder = 0 is equivalent to q divides m.

    Mo(m) = 0 <-> m is prime (no values of q satisfy "q divides m")
    Mo(25) = q2·!q1   <-> (101 = 5 is the only factor of m.)

    Where are the trivial solutions? Trivial solutions are filtered by the choice of fb. fb must be big enough to fit both factors but smaller that the number of bits of the module. The trivial solutions 1 and m do not satisfy Mo because m does not fit in fb bits.

    A curiosity: "What is Moaña?" Moaña (pronounce the ñ as the gn in Cognac), is a place (42º17'N 8º43'W) in Spain, my country. There is nothing special about the place, it is just that I happened to find this factoring model walking around Moaña in summer 2000. I had to verify it! I went into a local bookshop, bought a pen and a notebook, and checked the whole thing until dusk. It is so unusual for me to write on anything that is not a computer, that I kept that notebook for some time and thought about its contents as the Moaña formulae. I just got used to the name.

to the top

4.1 Formalization

The following notation is used by the SM1.0 parser/profiler written to operate with Moaña expressions:

CONSTANTS	No aliases are allowed. Constants are defined by their numeric value. Binary constants: 0 or 1 Longint constants: Any positive value from 0 to 2147483648 (2³¹)
VARIABLES	Variables are either vectors of binary values or vectors of longint values. Variables are identified by one letter (the entire vector) or one letter followed by a number (the index of the specified element). No spaces or brackets are required or allowed to separate the index. E.g. q0 is the least significant bit of a vector q. a11+q1·(q2+!e7) is a valid expression. The letters a, b, d, e, g, h, j, k, m, n, p, q, s, t, x, y, z are used to define vectors of binary values. (Only m, q, h & d are used by the Moaña formulae, the others may be used freely.) The letters c, f, i, l, o, r, u, v, w are used to define vectors of longint values. (Only c is used by the Moaña formulae, the others may be used freely.) Of course, variables may contain either constant values or valid expressions.
UNARY OPERATORS	The following three operators apply to the immediately following variable or expression in brackets. ! binary not. If applied to a longint, the returned result is binary. Only the least significant bit of the longint is considered. « Arithmetic shift to the left. Same as unsigned multiplication by 2. E.g. «3 returns 6 » Arithmetic shift to the right. Same as unsigned division by 2. E.g. »7 returns 3, »»8 returns 2
BINARY OPERATORS	The following four operators apply between the previous variable or expression in brackets and the following. · Binary and. E.g. q11·q7 is a valid expression. q2·!q2 returns 0. If applied to longint, converts the result to binary. + Binary or. De Morgan in this notation: q1+q2 = !(!q1·!q2). If applied to longint, converts the result to binary. × Binary xor. q1×q2 = (q1+q2)·!(q1·q2) = q1·!q2+!q1·q2.If applied to longint, converts the result to binary. ± Arithmetic sum. E.g. 1±0±0±1±0 returns 2. Also, 7±11±2 returns 20. If applied to binary variables, their 1 or 0 values are treated as longint. The result is always longint.
BRACKETS	Two types of brackets are used: Local brackets: ( and ) are used as in any normal notation to change evaluation priority. Global brackets: Only < is used. It means, all the remaining expression acts as an atom until the end. q1·(q2+q3) = q1·<q2+q3 Since expressions may contain thousands of characters, this notation immediately shows that q1 "ands" the whole expression.
PRIORITY	Unless otherwise indicated by local or global brackets, there are three levels of priority: ! « » Maximum · Medium + × ± Lowest !q1·q2·q3+!q1·!q2·q3 is the same as (!(q1)·q2·q3)+(!(q1)·!(q2)·q3). Needless brackets are removed automatically.

The Moaña formulae in the previous notation are:

m (The module)	Since m is known (the number we pretend to factor), it is replaced by the constants values 0 or 1 bit by bit before starting the analysis. It can also be left unknown by just assigning variable names m1, m2, m3, ... to the vector. (m0 is assumed to be 1, since RL division is not defined for even numbers.)
q (The factor)	The factor is usually unknown. The vector fields are filled with 1, q1, q2, q3, ... (q0 is 1 as mentioned) before starting the analysis.
c (Carried product)	This is the only vector of longint. All the others are vectors of boolean. The carried product of d and q is derived from the extended product. The extended product is e_n = S (i=0,n) of d_i·q_n-i The extended product makes sense by itself and has interesting properties, the carried product does not make sense by itself, but its least significant bit is equal to the corresponding bit of the arithmetic product (the ordinary product). D e f i n i t i o n : if n=0 c_o = 1 else c_n = ( S (i=0,n) of d_i·q_n-i)±»c_n-1 E.g. c3 is d0·q3±d1·q2±d2·q1±d3·q0±»c2 (The S notation is not understood by the SM system. A Pascal procedure creates all "d0·q3±d1·q2±d2·q1±d3·q0±»c2 "-like expressions before starting the analysis.)
h (Incomplete carried product)	This is the carried product of d and q computed up to the previous bit (i.e. n-1) and applied to n. Since only the least significant bit is interesting, its is converted to binary by an AND operation. D e f i n i t i o n : case n=0 h_o = 1 case n=1 h₁ = 0 else h_n = 1·((S (i=1,n-1) of d_i·q_n-i))±»c_n-1) E.g. h3 is 1·(d1·q2±d2·q1±»c2) (The S notation is not understood by the SM system. A Pascal procedure creates all "1·(d1·q2±d2·q1±»c2) "-like expressions before starting the analysis.)
d (The RL division)	Is the RL division of m by q. D e f i n i t i o n : d_n = h_n×m_n×q_n E.g. d3 is h3×m3×q3
fb (Factor bits)	Is the number of bits of the factor. Of course, it has to be guessed. The smaller the better. It can obviously not be smaller than the number of bits of the module/2 and should not be as big, since it would make the trivial divisors 1 and m a solution of Mo.
Mo (Moaña)	As mentioned, Mo is the analytic factorization of a number. D e f i n i t i o n : Mo = AND(i=fb, 2fb - 1) of !d_i E.g. if fb = 6 then Mo = !d6·!d7·!d8·!d9·!d10·!d11 If the number is prime, Mo = 0, else Mo is the product sum of all its factors fitting in fb bits (factor and cofactor).

    Example: Let's factor a simple number with 5 unknown bits for the factors (fb = 6) m = 2257

    The module as an array of bits is m0 = 1, m1 = 0, m2 = 0, m3 = 0, m4 = 1, m5 = 0, m6 = 1, m7 = 1, m8 = 0, m9 = 0, m10 = 0, m11 = 1.
    The factor has 5 unknown bits q0 = 1, q1 = q1, q2 = q2, q3 = q3, q4 = q4, q5 = q5, q6 = 0, q7 = 0, q8 = 0, q9 = 0, q10 = 0, q11 = 0.

    The initial expressions for c, h and d are:

c0 = 1 c1 = d0·q1±d1·q0±»c0 c2 = d0·q2±d1·q1±d2·q0±»c1 c3 = d0·q3±d1·q2±d2·q1±d3·q0±»c2 c4 = d0·q4±d1·q3±d2·q2±d3·q1±d4·q0±»c3 c5 = d0·q5±d1·q4±d2·q3±d3·q2±d4·q1±d5·q0±»c4 c6 = d0·q6±d1·q5±d2·q4±d3·q3±d4·q2±d5·q1±d6·q0±»c5 c7 = d0·q7±d1·q6±d2·q5±d3·q4±d4·q3±d5·q2±d6·q1±d7·q0±»c6 c8 = d0·q8±d1·q7±d2·q6±d3·q5±d4·q4±d5·q3±d6·q2±d7·q1±d8·q0±»c7 c9 = d0·q9±d1·q8±d2·q7±d3·q6±d4·q5±d5·q4±d6·q3±d7·q2±d8·q1±d9·q0±»c8 c10 = d0·q10±d1·q9±d2·q8±d3·q7±d4·q6±d5·q5±d6·q4±d7·q3±d8·q2±d9·q1±d10·q0±»c9 c11 = d0·q11±d1·q10±d2·q9±d3·q8±d4·q7±d5·q6±d6·q5±d7·q4±d8·q3±d9·q2±d10·q1±d11· q0±»c10 h0 = 1 h1 = 0 h2 = 1·((d1·q1)±»c1) h3 = 1·((d1·q2±d2·q1)±»c2) h4 = 1·((d1·q3±d2·q2±d3·q1)±»c3) h5 = 1·((d1·q4±d2·q3±d3·q2±d4·q1)±»c4) h6 = 1·((d1·q5±d2·q4±d3·q3±d4·q2±d5·q1)±»c5) h7 = 1·((d1·q6±d2·q5±d3·q4±d4·q3±d5·q2±d6·q1)±»c6) h8 = 1·((d1·q7±d2·q6±d3·q5±d4·q4±d5·q3±d6·q2±d7·q1)±»c7) h9 = 1·((d1·q8±d2·q7±d3·q6±d4·q5±d5·q4±d6·q3±d7·q2±d8·q1)±»c8) h10 = 1·((d1·q9±d2·q8±d3·q7±d4·q6±d5·q5±d6·q4±d7·q3±d8·q2±d9·q1)±»c9) h11 = 1·((d1·q10±d2·q9±d3·q8±d4·q7±d5·q6±d6·q5±d7·q4±d8·q3±d9·q2±d10·q1)±»c10) d0 = h0×m0×q0 d1 = h1×m1×q1 d2 = h2×m2×q2 d3 = h3×m3×q3 d4 = h4×m4×q4 d5 = h5×m5×q5 d6 = h6×m6×q6 d7 = h7×m7×q7 d8 = h8×m8×q8 d9 = h9×m9×q9 d10 = h10×m10×q10 d11 = h11×m11×q11

The program replaces and simplifies for increasing n in order h, d, c:

h0 = 1 d0 = 1 c0 = 1 h1 = 0 d1 = q1 c1 = «q1 h2 = 0 d2 = q2 c2 = q2±q1·q1±q2±q1 h3 = q1×q2 d3 = q1×q2×q3 c3 = q3±q1·q2±q2·q1±(q1×q2×q3)±»<q2±q1·q1±q2±q1 h4 = !q1·q3·!q2+q1·!q3·q2 d4 = q4×!<!q1·q3·!q2+q1·!q3·q2 c4 = q4±q1·q3±q2·q2±(q1×q2×q3)·q1±(q4×!(!q1·q3·!q2+q1·!q3·q2))±»<q3±q1·q2±q2·q1±(q1Œq2Œq3)± »<q2±q1·q1±q2±q1 h5 = q1·!q4·q2·!q3+!q1·q4·!q2·q3 d5 = q5×<q1·!q4·q2·!q3+!q1·q4·!q2·q3 c5 = q5±q1·q4±q2·q3±(q1×q2×q3)·q2±(q4×!(!q1·q3·!q2+q1·!q3·q2))·q1±(q5×(q1·!q4·q2·!q3+!q1·q4·!q2· q3))±»<q4±q1·q3±q2·q2±(q [Truncated] h6 = q1·!q5·!q2·!q4·!q3+!q1·q5·!q2·!q4·!q3+!q1·q5·q2·!q4·!q3+q1·!q5·!q2·q4·!q3+!q1·q5·!q2·q4·!q3+!q1· q5·q2·q4·!q3+q1·q5· [Truncated] d6 = !<q1·!q5·!q2·!q4·!q3+!q1·q5·!q2·!q4·!q3+!q1·q5·q2·!q4·!q3+q1·!q5·!q2·q4·!q3+!q1·q5·!q2·q4·!q3+!q1· q5·q2·q4·!q3+q1·q [Truncated] c6 = q1·q5±q2·q4±(q1×q2×q3)·q3±(q4×!(!q1·q3·!q2+q1·!q3·q2))·q2±(q5×(q1·!q4·q2·!q3+!q1·q4·!q2·q3))· q1±!(q1·!q5·!q2·!q4·!q [Truncated] h7 = !<!q2·!q5·!q1·!q3·!q4+!q2·q5·!q1·!q3·!q4+!q2·!q5·q1·!q3·!q4+!q2·!q5·!q1·q3·!q4+q2·!q5·!q1·q3·!q4+q2· q5·!q1·q3·!q4+! [Truncated] d7 = !q2·!q5·!q1·!q3·!q4+!q2·q5·!q1·!q3·!q4+!q2·!q5·q1·!q3·!q4+!q2·!q5·!q1·q3·!q4+q2·!q5·!q1·q3·!q4+q2· q5·!q1·q3·!q4+!q2 [Truncated] c7 = q2·q5±(q1×q2×q3)·q4±(q4×!(!q1·q3·!q2+q1·!q3·q2))·q3±(q5×(q1·!q4·q2·!q3+!q1·q4·!q2·q3))· q2±!(q1·!q5·!q2·!q4·!q3+!q1· [Truncated] h8 = q1·!q2·!q3·!q5·!q4+!q1·q2·!q3·!q5·!q4+q1·q2·q3·!q5·!q4+!q1·q2·q3·q5·!q4+q1·q2·!q3·!q5· q4+!q1·!q2·q3·!q5·q4+q1·!q2·q [Truncated] d8 = q1·!q2·!q3·!q5·!q4+!q1·q2·!q3·!q5·!q4+q1·q2·q3·!q5·!q4+!q1·q2·q3·q5·!q4+q1·q2·!q3·!q5· q4+!q1·!q2·q3·!q5·q4+q1·!q2·q [Truncated] c8 = (q1×q2×q3)·q5±(q4×!(!q1·q3·!q2+q1·!q3·q2))·q4±(q5×(q1·!q4·q2·!q3+!q1·q4·!q2·q3))·q3± !(q1·!q5·!q2·!q4·!q3+!q1·q5·!q2 [Truncated] h9 = !q4·!q1·!q3·q2·!q5+!q4·q1·!q3·q2·!q5+q4·q1·!q3·q2·!q5+!q4·!q1·q3·q2·!q5+!q4·!q1·!q3·!q2·q5+q4·!q1· !q3·!q2·q5+q4·q1· [Truncated] d9 = !q4·!q1·!q3·q2·!q5+!q4·q1·!q3·q2·!q5+q4·q1·!q3·q2·!q5+!q4·!q1·q3·q2·!q5+!q4·!q1·!q3·!q2·q5+q4·!q1· !q3·!q2·q5+q4·q1· [Truncated] c9 = (q4×!(!q1·q3·!q2+q1·!q3·q2))·q5±(q5×(q1·!q4·q2·!q3+!q1·q4·!q2·q3))·q4±!(q1·!q5·!q2·!q4·!q3+!q1·q5· !q2·!q4·!q3+!q1·q [Truncated] h10 = !q5·q1·!q4·!q2·!q3+!q5·!q1·q4·!q2·!q3+q5·q1·q4·!q2·!q3+!q5·q1·q4·q2·!q3+!q5·!q1·!q4·!q2·q3+!q5· !q1·q4·!q2·q3+q5·!q [Truncated] d10 = !q5·q1·!q4·!q2·!q3+!q5·!q1·q4·!q2·!q3+q5·q1·q4·!q2·!q3+!q5·q1·q4·q2·!q3+!q5·!q1·!q4·!q2·q3+!q5· !q1·q4·!q2·q3+q5·!q [Truncated] c10 = (q5×(q1·!q4·q2·!q3+!q1·q4·!q2·q3))·q5±!(q1·!q5·!q2·!q4·!q3+!q1·q5·!q2·!q4·!q3+!q1·q5·q2·!q4· !q3+q1·!q5·!q2·q4·!q3+ [Truncated] h11 = !q1·q5·!q2·!q4·!q3+!q1·q5·q2·!q4·!q3+q1·q5·q2·!q4·!q3+q1·!q5·q2·q4·!q3+!q1·q5·q2·q4·!q3+!q1· !q5·!q2·!q4·q3+q1·q5·! [Truncated] d11 = !<!q1·q5·!q2·!q4·!q3+!q1·q5·q2·!q4·!q3+q1·q5·q2·!q4·!q3+q1·!q5·q2·q4·!q3+!q1·q5·q2·q4·!q3+!q1· !q5·!q2·!q4·q3+q1·q5 [Truncated] c11 = !(q1·!q5·!q2·!q4·!q3+!q1·q5·!q2·!q4·!q3+!q1·q5·q2·!q4·!q3+q1·!q5·!q2·q4·!q3+!q1·q5·!q2·q4·!q3+!q1· q5·q2·q4·!q3+q1· [Truncated]

    After that, the program writes Mo:

    Mo = !d6·!d7·!d8·!d9·!d10·!d11

    replaces:

Mo = !!(q1·!q5·!q2·!q4·!q3+!q1·q5·!q2·!q4·!q3+!q1·q5·q2·!q4·!q3+q1·!q5·!q2·q4·!q3+!q1·q5·!q2·q4·!q3+!q1· q5·q2·q4·!q3+q1·q5·q2·q4·!q3+· [Truncated]

    and simplifies:

    Mo = !q1·q5·q2·<q4×!q3

    Since q0 = 1, the values of q satisfying Mo = 1 are those making q3=q4, q2=q5=1 and q1=0. I.e., 100101 (=37) and (111101 (=61).

    The only divisors of 2257 are 37 and 61. (Note that 1 and 2257 have been filtered by the condition fb=6.)

    This example runs in less than a second on a slow (PII-400) PC. (Done in 0.946 sec.)

    Example 2: With only 9 unknown bits, just 4 more than the preceding example, let's factor (fb = 10) m = 537701

    m0 = 1, m1 = 0, m2 = 1, m3 = 0, m4 = 0, m5 = 1, m6 = 1, m7 = 0, m8 = 0, m9 = 0, m10 = 1, m11 = 0, m12 = 1, m13 = 1, m14 = 0, m15 = 0, m16 = 0, m17 = 0, m18 = 0, m19 = 1

    As in the previous example, the program replaces and simplifies for increasing n in order h, d, c:

h0 = 1 d0 = 1 c0 = 1 h1 = 0 d1 = q1 c1 = «q1 h2 = 0 d2 = !q2 c2 = 1±«q1 h3 = 0 d3 = q3 c3 = q3±q1±q3±»<1±«q1 h4 = q1×q3 d4 = q1×q3×q4 c4 = q4±q1·q3±q3·q1±(q1×q3×q4)±»<q3±q1±q3±»<1±«q1 h5 = !q1·q4·!q3+q1·!q4·q3 d5 = q5×!<!q1·q4·!q3+q1·!q4·q3 c5 = q5±q1·q4±!q2·q3±q3·q2±(q1×q3×q4)·q1±(q5×!(!q1·q4·!q3+q1·!q4·q3))±»<q4±q1·q3±q3·q1± (q1×q3×q4)±»<q3±q1±q3±»<1±«q1 ...

    The beginning seems very easy, but reaching c19 requires about an hour on the same machine on which the previous example ran in one second.

    As in the previous example, the program writes Mo:

    Mo = !d10·!d11·!d12·!d13·!d14·!d15·!d16·!d17·!d18·!d19

    replaces:

Mo = !(!q1·!q9·!q2·!q8·!q3·!q7·!q4·!q6·!q5+q1·q9·!q2·!q8·!q3·!q7·!q4·!q6·!q5+q1·!q9·q2·!q8·!q3· !q7·!q4·!q6·!q5+!q1·q9·q2·!q8·! [Truncated]

    and simplifies:

    Mo = q1·q9·!q3·<q2·q8·q7·q4·q6·!q5+!q2·!q8·!q7·!q4·!q6·q5

    Since q0 = 1, the values of q satisfying Mo = 1   1?????0?11 and (?11101?1?? or ?00010?0??) = 1111010111 and 1000100011 = 983 and 547

    The only divisors of 537701 are 983 and 547. (Done in 3890.871 seconds.)

to the top

4.2 A syntactic approach: The parser

    Previous examples show how fast computing time increases with input size when evaluating Mo(m).

    To help understanding what is happening, some explanation is required about how a parser works.

    The parser just reads the expression from left to right in a single pass. While it reads, it pushes the constants and variables into a stack and pushes the operators into a different stack. It also considers priority and bracket level and, every time a new operator does not increment this level, it forces a calculator to compute operations that are pending in the stack.

    Simplifying: Assuming the number of operators is proportional to the length of the expression, and the calculator performs all operations in equal time, it can be considered that time for parsing an expression is proportional to the length of the expression.

    Concluding: It is the length of the expressions what increases exponentially.

    Why does length increase?

    Partially because expressions are not simplified to their optimal size, but also because they are inherently complicated.

    Note that the apparent simplicity of Mo = !d6·!d7·!d8·!d9·!d10·!d11 and the fact that it has only a few solutions (as many as q factors satisfy Mo(m)=1) is disguising the fact that any of its bits d6 ... d11 are 50% of the times 1 and 50% of the times 0. But only q values corresponding to the factors satisfy that all its d_i terms are simultaneously 0. The expressions of individual bits are necessarily long. Imagine the case of 20 variables (2²⁰ is approx. 10⁶) any of the expressions is half a million times 1 and half a million times 0, which means they are as long as the product sum of half a million 20-variable AND terms ORed. Mo(m) of twenty variables is the AND of 20 expressions of half a million terms of 20 variables each. But, when simplified, it is just a product sum of two 20-variable factors (assuming m has only 2 factors). The point is: Mo is dramatically simplified, but previous d_i terms cannot be.

    Why are expressions not simplified to their minimum size?

    Parsing (analyzing syntactically) an expression is not enough. To really simplify an expression it requires profiling (analyzing semantically).

    The only thing the calculator does with the expression is:

    Binary operators:

        constant operator constant       -> computes the result
        constant operator expression    -> simplifies: sometimes to constant and sometimes to expression (E.g.: 1·q1 -> q1, 0·q1 -> 0, 1+q1 -> 1, 0+q1 -> q1)
        expression operator expression -> just copies

    Unary operators:

      operator constant        -> computes the result
      operator expression    -> seldom simplifies (E.g. !!q1 -> q1), most frequently appends the operator to the expression.

    The parser is also used to remove a variable from an expression. If the profiler decides that a variable has a known effect on the result (Nothing, inversion, AND, NAND, OR, NOR) it replaces it either by 1 or by 0 depending on the case, and re-parses the expression. It these cases the parser succeeds in returning a simpler expression with one variable less.

    The SM1.0 parser/profiler used in the examples tries to find a balance between expression size and simplification effort, note that:

    Parsing requires some time approximately proportional to the length of the expression.
    Profiling requires some time approximately exponential to the number of different variables in the expression.

to the top

4.3 A semantic approach: The profiler

    A previous note: Many authors mention an inherent limitation of computers: the fact that they only manipulate symbols in abstraction of any possible meanings. Therefore, claiming something as semantic analysis using a computer is contradictory and pretentious. They are right if we consider a computer analyzing most subjects. One can argue that even if we plug-in some weird hardware to let a computer "taste an apple" any data the computer may have associated to the symbol "apple" cannot seriously be called a semantic field. I think boolean expressions are just The exception. A computer can compute truth tables, which is the essence of profiling, and truth tables are essentially "the meaning" of boolean expressions. This is why I claim my profiler as a semantic analyzer.

    As mentioned, what the profiler does is computing truth tables for all possible input values of the expressions. First, the expression is converted to a form in which replacing the variables by constants is much faster. These replaced versions of the expression are computed using a special fast parser that only operates with constants. What the profiler analyzes is the behavior of the result in relation with any of the input variables.

    There are six easy cases for a particular input variable v.

      1. The result for v=1 is always the same as the result for v=0. The function does not depend on v, v can be replaced by 0 and the expression is parsed again to make it simpler.
      2. The result for v=1 is always the opposite of the result for v=0. The function is inverted by v. v can be replaced by 0 the expression is parsed again to make it simpler and the resulting expression is v×<s where × is XOR, < is a global bracket, s is the result of the simplified expression returned by the parser.
      3. If v=1, the result is always 1. v ORs the whole expression. Same as before. We get v+<s
      4. If v=0, the result is always 0. v ANDs the whole expression. Same as before. We get v·<s but this time s is obtained by replacing v by 1 (instead of 0) and parsing.
      5 and 6. If v=1, the result is always 0, If v=0, the result is always 1. !v ANDs the expression and !v ORs the expression . The same.

    Of course, more could be done: Analyzing the behavior of the result in relation with v·w, v+w, v×w, ... functions of 3 variables, etc. This is not done by my profiler. Remember that the argument concerning the bits of Mo individually (exposed in the previous point) leaves no margin to expect the expressions to keep simple no matter how they are optimized.

    What the profiler also does is checking if the result has few 1s or few 0s compared to the size of the table. If it is so, the function is replaced by a product sum or an inverted product sum. A product sum is the basic brick of programmable logic and it is the OR of ANDed terms. E.g. q4·q3·!q2·q1 + !q4·q3·!q2·q1 + !q4·q3·q2·!q1 is a product sum of three terms producing 3 1s from a total of 16 table places (produced by 4 variables).

    Serious criticism can be expressed to the whole Moaña system: If profiling is done by building truth tables, the whole think is just a "brute force" attack. Not only brute force, but brute force on the slowest possible form of the problem, with exponential memory requirements, and without any arithmetic shortcut.

    I never claimed Moaña as a practical factoring method, except on a quantum machine, but as a way to get some light on the subject and to think about factoring and other Number Theory problems.

    "As for instance ..."

    The Go(n) function: Go(n) = AND (i=2 to n/2) of (Mo(i)+Mo(n-i))=/=0

    It is obvious that for small values of n, Go(n) -> n0

    "Excuse me, but your use of the word obvious is making me a little nervous. What is obvious in Go(n) -> n0?"

    It is obvious that i + (n - i) = n and that a that number satisfying Mo(i)=0 is prime. Therefore, a number n satisfying (Mo(i)+Mo(n-i))=0 for some i can be expressed as the sum of two primes. I.e., a number satisfying Go(n) = 0 can be expressed as the sum of two primes. A number satisfying Go(n) = 1 can not be expressed as the sum of two primes. n0 is the least significant bit of n, n0=1, or just n0, means a numbers is odd.

    Go(n) -> n0 means all numbers which cannot be expressed as the sum of two primes are odd. This is Goldbach's conjecture. I did not verify it, but I assume it has been done for small numbers.

    "But this includes even numbers and Mo is not defined for even numbers."

    Correct, but I generalize Mo(n) now:
        If n is even, if n=2, Mo = 1 else Mo = 0
        If n is odd, Mo = the previously defined Mo.

    "You mean I only have to replace and simplify, and I have proved Goldbach's conjecture?"

    Your words. Only. Those who think so, goto 4.2 again and read carefully.

    Seriously, I don't know any application of Moaña to other problems.

to the top

4.4 A probabilistic approach: Independence

    An other way to approach Moaña formulae could be:

    "If the SM1.0 parser/profiler can manage Moaña with 512 bits or more to verify a given solution as big as the factors of RSA155, but can only manage 10 to 15 unknown bits, why don't we give it probabilistic values (which are constants)? This way, it will be able to manage 512 bit numbers and more."

    Let's define: q1 = 0 as q1 IS 0, q1 = 1 as q1 IS 1 and q1 = 0.5 as q1 has 50% of chances of being 1.

    Since the probability of !a being one is: 1 minus the probability of a being one.
    And the probability of a·b being 1 is the product of the probabilities of a and b being 1.

    With NOT an AND we can compute any boolean operation. OR (applying De Morgan) is !(!a·!b), XOR is !a·b+a·!b, etc.

    We will replace a particular bit by a guessed constant 0 or 1 and all the others by 0.5.

    Then, compute Moaña and:
    if Mo(m) = 0, the guess was wrong, we toggle the bit.
    if Mo(m) > 0, the guess was right, we keep the bit.

    Knowing one bit, we repeat this procedure nb times until we know all the bits.

    Although Mo will be very small (around 2^-512 for 512 bits), it is in range of IEEE extended floating point. If it wasn't, we could always create our own real types with gigantic exponents even if that would slow down somewhat.

    What is wrong this time? Not the PZCS again?

    No. Not the PZCS. The wrong statement is: " ... the product of the probabilities of a and b being 1"

    Problem: If the probability of a being 1 is 1/2 and the probability of b being 1 is 1/2, what is the probability of a·b being 1?

    The correct answer is:

    Something between 1/2 (for the particular case a=b) and 0 (for the particular case a=!b) which depends on the relation between a and b.
    If a and b are independent, which was not specified above, and in general they are not, then the probability of a·b is 1/4.

    How could we compute these probabilities correctly? By finding out the precise relations between the variables using (oh no!) truth tables.

to the top

4.5 A quantum approach: A letter to Santa Claus

    The previous (probabilistic) approach was, again, not "the one". Why should this one be an exception? This one has an important advantage: Quantum computers do not exist. We can speculate about how they should be.

    For instance: I want my quantum computer blue and orange and with a label showing: " CAUTION: Do not open the cover while the machine is in superposition. "

    Or seriously: I want a machine that inverts product terms. The quantum part of a computer, the whole computer does not need do be "quantum", is a stack of n qbit wide registers. Those registers can calculate just one unary operation, inversion, and just one binary operation (no matter which, all others can be obtained by simple equivalencies). The whole operation works as the usual Moaña system, just the parser (no profiler is required). The conventional part of the computer parses conventional expressions: Pushes product terms to the stack and triggers calculations.

    So, what is the difference? You can invert product terms (E.g. q3·!q1·q0) on a conventional computer?

    Yes, but you get 7 product terms.

    !(q3·!q1·q0) = q3·q1·q0 + q3·q1·!q0 + q3·!q1·!q0 + !q3·q1·q0 + !q3·q1·!q0 + !q3·!q1·q0 + !q3·!q1·!q0

    What I expect of a quantum machine is: You load the term in the register: [-][1][-][0][1] represents q3·!q1·q0 in a 5 qbit register. The contents is now discrete and therefore, readable. Then you invert it. The result is [X][X][X][X][X], a superposition of all q3·q1·q0 + q3·q1·!q0 + q3·!q1·!q0 + !q3·q1·q0 + !q3·q1·!q0 + !q3·!q1·q0 + !q3·!q1·!q0 states which still fits in a single register. It cannot be read, but it can be used as an operand for a calculation. It can compute operations with other registers either in discrete or in superposed states. At the end of the calculation, either a discrete state is obtained or one can be forced by speculating with the values of particular bits. This can be done performing AND operations with chosen discrete registers.

    Moaña formulae in this machine do not grow because, after parsing an expression, the result always fits in a single register. This also happens in a conventional computer when operating with constant values, but not when operating with variables. When operating with variables the result is an exponentially growing expression, as mentioned.

    All what the machine requires is a conventional parser and a stack of quantum registers containing superposed results of operations with product terms.

    The idea lying behind this machine is the idea lying behind any quantum speculation:

    If all the cases computed for all combinations of n variables (which are 2ⁿ):

        q3 = 0000000011111111
        q2 = 0000111100001111
        q1 = 0011001100110011
        q0 = 0101010101010101

    could be operated together, problems requiring exponential time could be done in P.

    Nobody knows today what the future of quantum computing will be. A historical remark: Quantum computing (the idea of) was born after the nobel prize winner Richard Feynman proved that conventional computers could not predict the behavior of quantum models in P because of the inherent complexity of those models. The origin of this subject is a limitation of computers, not an amazing faculty. The argument was reversed and formulated as: "If the properties of Quantum Physics could be used for computing, mathematical problems growing exponentially could, in many cases, be done in P." Peter Shor wrote a paper (available online) titled "Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer", which intensified research on quantum computers. This paper is a strict proof, according to present-time Quantum Physics, that such algorithms exist for quantum computers. My approach is not strict at all, but it helps understanding that this is not a surprise at all. What would be a surprise is that a 512 qbit wide quantum register could be built.

    Quantum computing looks too good to be true. Maybe it finally is, or maybe someone draws the limit with some law as "A quantum register of n qbits requires, at least, 2ⁿn^-1seconds to compute a calculation involving all its possible states." which would make it all useless, but compatible with both existing and not-existing conservation laws.

to the top

5. The CRAB (Crawling Reversible Automat Body)

In chapter 3 the concept periodic form was introduced. I repeat it now because the remaining part of this article is about periodic forms.

1 RLdiv n is the modular inverse of n modulo 2^k.

    For the particular case k = ¥ , 1 RLdiv n is called the periodic form (PF) of n.

    The periodic form of a number n, PF(n) is a number created by the infinite repetition of a constant pattern, satisfying:

      (n·PF(n)) mod 2^¥ = 1    (The symbol · is multiplication. No boolean notation is used in the remaining part of this article.)

PF(n) = 1 RLdiv n computed for an ¥ number of bits.

    The periodic form is computed by a crab machine that writes it on an endless tape of 0s and 1s. The tape starts with a 1 followed by an infinite number of 0s that will be replaced by the PF. The machine does a simple calculation writes one bit, crawls 1 bit to the right, and repeats the process. Since the same algorithm used to compute the periodic form of a number can be used to compute the number from the first nb bits of the periodic form, it is called reversible.

    The simplest possible crab has only a carry register, initially loaded with 0. The crab counts the number of 1s that are in front of its "input tentacles" (I really hope no biologist is reading this!) and adds it to its carry register. If the result is odd, it writes a 1. If it is even, a 0. Its "output tentacle" is placed to the right of the input tentacles. Then, it shifts the carry register one bit to the right and crawls one bit to the right. This is repeated endlessly.

    Objection: It is reading its own output! Yes. That's the idea.

    Where is the number? The number is encoded in the distance between its input tentacles. Write the number in binary. For each bit being 1 put one input tentacle at the corresponding position. For each 0, no tentacle.

    When does it stop? Never. I mentioned "the simplest possible" crab. This one doesn't stop. The next one will.

    Also, this time instead of talking about input tentacles, I will talk about counting the number of 1s in the result of a binary AND operation. Of course, both crabs produce the same output, because:

Any odd number n of bit length nb has only one periodic form PF(n). I.e., one unique inverse modulo 2^¥.

The crab described as pseudocode is:

    write tape_o = 1
    let carry = 0                  // Carry register
    let ncoo = 0                   // Number of Consecutive Output Ones
    let nb = number of bits of n
    let tpi = 1                    // tape index of output bit being written, tape_o = 1
    loop
        let carry = (carry DIV 2) + SUM(i=1 to nb-1) of n_i and tape_tpi-i        if carry is odd
        begin
            write tape_tpi = 1
            let carry = carry + 1
            let ncoo  = ncoo + 1
        end
        else begin
            write tape_tpi = 0
            if  ncoo = nb - 1 then Halt
            let ncoo = 0
        end
        let tpi = tpi + 1
    end

The only part requiring some extra attention is:

        let carry = (carry DIV 2) + SUM(i=1 to nb-1) of n_i and tape_tpi-i

    1. This counts the number of simultaneous 1(in n) 1(in the tape) occurrences. (The counting AND)
    2. i starts with 1 instead of 0, because there is one value missing, which depends on the output at tpi calculated just after. This is the reason why: if tape_tpi = 1, carry is increased afterwards to compensate this.
    3. Tape of any negative indices produced when tpi < nb should be assumed = 0

    The first fact that can be noticed from the description of the crab is: All periodic forms end with a sequence of nb-1 ones followed by a zero. Therefore, searching this sequence is the only halting condition required.

    Notation: All periodic forms start with a 1 written in the first line of the algorithm. It is the 1 corresponding to the least significant bit of 1 RLdiv n for an odd n. This 1 is not repeated, the PF starts with the digit after it. In the following, this 1 in not written and the PF is usually represented using characters as * or # for 1 and _ for 0. Only when arithmetic operations are performed with PFs, the 1 is written and (0, 1) characters are used.

    Example:


    PF( 3) = *-
    PF( 5) = -**-
    PF( 7) = **-
    PF( 9) = --***-
    PF(11) = *---*-***-
    PF(13) = -*---**-***-
    PF(15) = ***-
    PF(17) = ---****-
    PF(19) = *-**----*-*--****-
    PF(21) = -****-
    PF(23) = **--*-****-
    PF(25) = --*-*----***-*-****-
    PF(27) = *--*----*-**-****-
    PF(29) = -*-**---*----**-*--***-****-
    PF(31) = ****-

to the top

5.1 Three aspects of the same problem

    In the article "All Fermat and Mersenne numbers are squarefree", ß(n) was defined as "the order of the subgroup of the powers of 2 modulo n". It has also been mentioned that ß(n) is the period of the digits after the point of 1/n written in binary. In chapter 3 it was introduced that ß(n) is the length of the repeated pattern of PF(n). What this point introduces is that, not only the length of such periods, but the content of these three aspects of the problem is the same as well.

    Let's see this with one example, n=11:

        1/11 = 0.0001011101 0001011101 0001011101 ...

        The powers of 2 modulo 11 are:

        1), (2, 4, 8, 5, 10, 9, 7, 3, 6, 1), (2, 4, 8, 5, 10, 9, 7, 3, 6, 1), (2, 4, 8, 5, 10, 9, 7, 3, 6, 1), ...

        Blue numbers are 2 times their predecessors, red numbers are 2 times their predecessors minus n. Since this is the basic procedure of division, it is not a surprise that these colors correspond with those of the 0s and 1s of 1/11.

        1/11 = 0.000 10 1110 1000 10 1110 1000 10 1110 1 ...

        PF(11) = *---*-***-

        Before concluding too fast, note that 2^{ß(11) /2}= 10 = -1 mod 11. This means 11 is antisymmetric. Its periodic form is a sequence of length ß(n)/2 followed by the same sequence inverted. It is too easy to find "some" correspondence between PF(11) and 1/11. Let's try a more complicated example.

        PF(23) = **--*-****-

        The powers of 2 modulo 23 are:

        1), (2, 4, 8, 16, 9,18, 13, 3, 6 , 12, 1), (2, 4, 8, 16, 9,18, 13, 3, 6 , 12, 1), (2, 4, 8, 16, 9,18, 13, 3, 6 , 12, 1), ...

        1/23 = 0.00001011001 00001011001 00001011001 ...

        It has already been mentioned that PF(n) ends with a sequence of nb-1 1s followed by one 0. It can also be noticed that 1/n starts with a sequence of nb-1 0s followed by one 1. It is that sequence which allows to establish the correct correspondence. The first "surprise" is that the correct correspondence is done inverting the bits of PF(n). After some analysis of the crab, this will no longer be a surprise, since the crab can easily invert the sequence only by changing the initial carry=0 by another value. Of course this is not a matter of doing "adjusting tricks" PF is defined as it should be:

    The only infinitely long periodic number satisfying: n·PF(n) mod 2^¥= 1

    The periodic binary representation of 1/n as 0.xxxxx is PF(n) with all its bits inverted and starting form the end (from the element ß-1), toward the beginning. The last element of PF (the element ß) is included in the second (and following) repetition(s), but not in the first one.

to the top

5.2 Reversibility of the algorithm

    The same linear algorithm (CRAB) used to compute PF of a number can be used to find out the number originating the PF.

    Method: The first thing that has to be determined is nb. As mentioned, PF(n) ends with an nb-1 long sequence of 1s. No other sequence of 1s in PF(n) can be longer or as long.

    1. nb = the number of 1s in the final sequence + 1
    2. Restore the initial 1 at the beginning of the PF, take nb bits.
    3. Compute the crab until nb only.

    The result is n.

    E.g.

    PF(n) = **--*-****-

    1. nb = 5    (The final sequence is 4 bit long.)
    2. The inverse of n modulo 2^¥= ... 01111010011 01111010011 01111010011 1 only nb bits are required.
    3. The first nb (5) bits of the modular inverse of: 0011 1 (5 bits) are: 10111 = 23

    n = 23

    A consequence of this is: "I f nb is known, the first nb bits of a PF fully represent the complete PF." All the other bits can be reconstructed from nb and the first nb bits. This can be done by computing backwards to get n and forward again to reconstruct the whole PF.

    All possible combinations of "first nb bits" can be represented as a valid PF of length ß >= nb corresponding to an nb bit long number.

to the top

5.3 Operation with periodic forms

     5.3.1. Periodic forms can be multiplied. PF(n)·PF(m) = PF(n·m)

    Multiplication is done as follows:

        1. Knowing n, m, ß(n), ß(m) compute ß(n·m). This can be done using the ß(aⁱ·b^j) = LCM(a^i-1·ß(a), b^j-1·ß(b)) formula. This multiplication method is not efficient, because it is only of theoretical interest.
        2. Starting with a 1, repeat both PFs as many times are required to get 2 ß(n·m) long numbers.
        3. Multiply the numbers normally.
        4. Again, remove the initial (least significant) 1.

    5.3.2. There is a PF called the neutral PF which is PF(1) = -

        ß(1) = 1
        PF(1)·PF(n) = PF(n)

    5.3.3. PFs can also be multiplied by numbers.

        Method for computing m·PF(n): Start the PF(n) with a 1 and repeat many times. Do ordinary multiplication by m. During multiplication, the period of the product has to be determined.

        If n and m are relatively prime, this period is ß(n).

        Obviously, n·PF(n) = PF(1)

        In general such expressions are: m·PF(n) = m RLdiv n = m·(1 RLdiv n)

        This chapter only studies expressions of the form PF(n) which is (considered) the interesting part of m·PF(n).

    5.3.4. Similarly, it may be argued that PFs may be divided and divided by numbers. This "arithmetic" could be used to give more academic proofs for the assertions made in this article and in "All Fermat and Mersenne numbers are squarefree" www.dybot.com/numbers/sqfree.htm. All assertions made in "All Fermat ..." are proved and proving all assertions of this article would make it unreadable.

to the top

5.4 Vertical analysis of the periodic form

d1 d2 d3 d4 d5 d6 d7 d8 d9 . . . - - - - - - - - - - - * - * - * - * - * - * * * - - * * - - * * * - * * - * * - * * * * * - - - * * * - - * - * * * - * - - - * * - * * * * - * * * - * * * * * * * - - - - * - - - - * - * * * - - * * * * - * - * * * * - - * - - - - * * * - - - - * - * * * - - - * - - * - * * * * - * * * * * * - -

"The truth is out there, Neo. It's looking for you and
it will find you, if you want it to." (The Matrix)

If all odd numbers qk·2^k + ... + q2·2² + q1·2¹ + 1 are written in order in a column and their periodic forms are written to the side of that column:

    3 : *-
    5 : -**-
    7 : **-
    9 : --***-
   11 : *---*-***-
   13 : -*---**-***-
   15 : ***-
   17 : ---****-
   19 : *-**----*-*--****-
   21 : -****-
   23 : **--*-****-
   25 : --*-*----***-*-****-
   27 : *--*----*-**-****-
   29 : -*-**---*----**-*--***-****-
   31 : ****-
   33 : ----*****-
   35 : *-*---*****-
   37 : -**-*-***-**-----**--*-*---*--*****-
   39 : **-*--*****-
   41 : --**-----***--*****-
   43 : *-----*-*****-
   45 : -*--*-*****-
   47 : ***--**-**---*-*-*****-
   49 : ---*-**---**-*-*****-
   51 : *-*****-

observing the periodic forms vertically, the following properties can be noticed.

5.4.1 The first two bits of the periodic form d are the two least significant non-trivial bits of the number q1 and q2. Any other bit of the periodic form is defined by the bits q1 to qk as: qk×<f(1..k-1) Where f(1..k-1) is a combinatory function of the bits q₁ .. q_k-1.

    d1 = q1
    d2 = q2
    d3 = q1×q2× q3
    d4 = q4×<!q1·q3·!q2+q1·!q3·q2
    d5 = q5×!<!q1·!q4·!q2·!q3+q1·q4·!q2·!q3+!q1·!q4·q2·!q3+q1·q4·!q2·q3+!q1·!q4·q2·q3+q1· q4·q2·q3
    ...
    dn = qn×< ...

These functions satisfy:

   a. The function is periodic of length 2^k.
   b. The second 2^k-1 bits are the first 2^k-1 bits inverted. This implies that there are the same number of zeros and ones. This is required by the bijective application between the numbers of length k and the first k bits of the set of all PFs. Any combination of k bits is the beginning of a valid periodic form corresponding to a k-bit long number.
   c. The first 2^k-1 bits produce a symmetric pattern (and the 2nd obviously too).

    5.4.1 For any two numbers a and b such that ß(a) = ß(b), a > b -> PF(a) > PF(b)

    Periodic forms are compared as binary numbers taking the first bit (even if represented to the left as a string) as the least significant. This theorem is rather obvious when nBits(a) =/= nBits(b), because the nBit-long sequence of 1s is the most significant part of PF(n), but it is fully valid, even if nBits(a) = nBits(b).

   E.g. 35 & 39:

                        #---##   35   :12:#-#---#####-
                        #--###   39   :12:##-#--#####-

35 < 39 the only difference is bit 2, computing the PF until bit 2 produces PF(35) #-#, PF(39) ##- , until then, PF(35) > PF(39), but the next bits will always correct this and, at the end, PF(35) < PF(39).

This is valid for any size, any ß & any nBits:

                 #-----##-##--##-#----###-#=   34445853   :36:-#-##-----#########################-
                 #----#-#----------#----#-#=   34865285   :36:-##--#----#########################-
                 #--#-#-#-#-####-#-#-#-##-#=   39156397   :36:-#--#--#--#########################-
                 #--#-####--###-##-#-######=   39745215   :36:#####--#--#########################-
                 #--###-#-###---##--#######=   41272959   :36:######-#--#########################-
                 #-#------#-#-#-#--#-##-#-#=   42030261   :36:-###--##--#########################-
                 #-#-#-##----------#-#-#-##=   44826795   :36:#-------#-#########################-
                 #-##-#-##-#-#-#--#####-#-#=   47622645   :36:-###-#--#-#########################-
                 #-###---##########-#---###=   48496455   :36:##-###--#-#########################-
                 #-####-#----------#-####-#=   49545405   :36:-#-#--#-#-#########################-
                 ##----------##----------##=   50343939   :36:#-#-#-#-#-#########################-
                 ##--#-#--##-##-##----#---#=   53065233   :36:---####-#-#########################-
                 ##-#-#---#----##--#-#--#-#=   55643301   :36:-##-#--##-#########################-
                 ##-##-##----------##-##-##=   57409755   :36:#--#-#-##-#########################-
                 ###-####-##--##-#-#---#--#=   62757513   :36:--###-###-#########################-

A proof for this could be found analyzing PF as the binary digits of 1/n.

to the top

5.5 Horizontal analysis of the periodic form

    5.5.1 As mentioned, all PFs end with a sequence of bn-1 successive 1s followed by one zero.

    E.g. The PFs of all 5 bit numbers end with (-)****-, 9 bit number with (-)********-, ... (-) means zero or nothing

    Any other sequence of consecutive 1s in the PF is shorter than this unique sequence.

    Any sequence of consecutive zeros in a PF is also shorter with only one exception. The only possible exception is an nbit-long sequence 000001 finishing exactly at the middle of the PF. After such a sequence, the second half of the PF is the repetition of the same pattern inverted. Numbers having such a PF are called antisymmetric. The point 5.6 of this article is entirely dedicated to antisymmetry.

    5.5.2 For any given length ß there exists at least one number n satisfying ß(n) = ß for each divisor of ß including 1.

    These PFs, called basic PFs, are made of a sequence of zeros of length divisor minus 1 followed by 1s to fill the complete length ß except the final 0.

    E.g. ß=15 : Divisors = 1, 3, 5

   ##############-  (1 -> 0 zeros to the left, total length = 15 matched by adding 1s)
   --############-  (3 -> 2 zeros to the left, total length = 15 matched by adding 1s)
   ----##########-  (5 -> 4 zeros to the left, total length = 15 matched by adding 1s)

The complete list of PFs whose ß is 15 is:

   number (bin)    number      ß   PF(n)
       #--#-### =    151(p) : 15 : ##--#--#######- (NOT generated by this rule)
       ##-##--# =    217    : 15 : --#-##-#######- (NOT generated by this rule)
    #----#----# =   1057    : 15 : ----##########-
  #--#--#--#--# =   4681    : 15 : --############-
############### =  32767    : 15 : ##############-

As shown above, the corresponding numbers are as 100100100 1. A 1 followed by j zeros, repeated k times, finished by 1.

ß((1 followed by j zeros) repeated k times and ended by 1) = (k+1)·(j+1)

These numbers may be prime (5, 7, 17) or not (9, 15, 21).

5.5.3 If ß = 2^k, to the previously defined basic PFs, a special set of PFs for all intermediate bit numbers is also valid, forming the recursive double A as shown below:

#-------# = 257(p) : 16 : -------########- ##------## = 771 : 16 : #-#-#-#########- #-#-----#-# = 1285 : 16 : -##--##########- ####----#### = 3855 : 16 : ###-###########- #---#---#---# = 4369 : 16 : ---############- ##--##--##--## = 13107 : 16 : #-#############- #-#-#-#-#-#-#-# = 21845 : 16 : -##############- ################ = 65535 : 16 : ###############- #---------------# = 65537(p) : 32 : ---------------################- ##--------------## = 196611 : 32 : #-#-#-#-#-#-#-#################- #-#-------------#-# = 327685 : 32 : -##--##--##--##################- ####------------#### = 983055 : 32 : ###-###-###-###################- #---#-----------#---# = 1114129 : 32 : ---####----####################- ##--##-