Period Finding in Modular Exponentiation

period_finding_in_modular_exponentiation.hvm1

// In this file, I explored the idea of computing the solution of:
// (3^x) % (2^s) == 1
// By using superpositions. The approach I used is to create an hand-optimized
// Mul3 function that seems to be efficient, and then creating a superposition
// of all Church Nats, as a perfect binary tree in the shape {{{0 1} {2 3}}...},
// and then applying that to `mul3` of `1`. As a result, we'll have a sup of all
// multiples of 3 (as binary strings). We can then call the function "Is1" on
// that sup. The result is a big superpositions of `0`, except for the places
// where we have a solution for the equation, which are `1`. This algorithm,
// despite all involved functions fusing, is exponential. After thinking about
// it, I realized the reason is that the tree of superposed Church numbers
// doesn't share redexes, since they're all isolated. What we should do,
// instead, is create a superposed multiples of 3 *directly.  That tree would
// have the following shape:
// (I
//   {(O
//     {(O
//       {(O {(O {(O ...) (O ...)}) (O {(I ...) (I ...)})})
//        (O {(I {(O ...) (O ...)}) (I {(I ...) (I ...)})})})
//      (O
//       {(I {(O {(O ...) (O ...)}) (O {(I ...) (I ...)})})
//        (I {(I {(O ...) (O ...)}) (I {(I ...) (I ...)})})})})
//    (I
//     {(O
//       {(O {(O {(O ...) (O ...)}) (O {(I ...) (I ...)})})
//        (O {(I {(I ...) (I ...)}) (I {(O ...) (O ...)})})})
//      (O
//       {(I {(I {(O ...) (O ...)}) (I {(I ...) (I ...)})})
//        (I {(O {(O ...) (O ...)}) (O {(I ...) (I ...)})})})})})
// If we collapsed this infinite superposition (to generate a list), we'd get:
// - 1
// - 11
// - 1001
// - 11011
// - 1000101
// - 11001111
// - 1001101101
// - 110100010001
// - 1000010110011
// - 110001110011001
// - 1001010101100111
// - 110111111100110101
// - 10001111110110000001
// - 110010111100101000011
// - 10011110110111110001001
// - 110101100100111101011011
// - 10000010111010110000100101
// - 110000111010000101001101111
// - 10010010100010011110100011101
// - 1101101111001101011000101010001
// - 10001001110110000010101111110011
// - 1100110101001010001111101111011001
// - 10011000000111110010111001110010111
// - ...
// Which is the binary expansion of every multiple of 3 (1, 3, 9, 27, 81...).
// If we, thus, applied `Is1` to the superposition, we'd have, once again, 0's
// everywhere, except for places where there is a solution for the original
// equation, which would be 0's. The difference, though, is that, now, we're
// sharing "falsifiable" digits, which allows all children of an incorrect
// branch to collapse to `0`, so we don't need to further compute this branch.
// In other words, unlike the former approach, the normalized superposition tree
// isn't exponential anymore. This would allow us to solve the equation
// sub-exponentially, in theory.
// 
// Sadly, the function I implemented to create the superposition of all
// multiples of 3 ('SlowGen') is, itself, exponential, possibly because I create
// many copies of `xs` and take the tail, possibly resulting in lots of useless
// duplications. If we find a faster / more direct algorithm to generate such
// tree, I believe we'd have a solution to this instance of DLP in polynomial
// time. This could then be generalized by:
// - 1. Generating a fast "mulN", for any N;
// - 2. Creating a var-base numeric system such that Π(bases) = N.
// 
// The step 2 is important as it allows us to to work on `mod N` without a
// modulus operation. For example, the var-base 30 system would be able to
// represent nums in the shape `{0|1|2|3|4}*6 + {0|1|2}*2 + {0|1}`, which is
// exactly the set of numbers from 0 til 30, thus, operations on that numeric
// system would be `mod 30` naturally. By doing these steps, we'd be able to
// efficiently solve `g^r % N == 1` for r, given any `g` and the factors of `N`.
// Note this is NOT a solution to the DLP problem (since we need the factors of
// `N`); it'd merely be a way to use a solution of integer factorization (of the
// modulus `N`) to find the period `r` of `a^r mod N`, i.e., converting a solution
// of one hard problem to another. (I find it important to include these obvious
// disclaimers because people WILL find ways to misinterpret...)

(O x) = λo λi λe (o x)
(I x) = λo λi λe (i x)
E     = λo λi λe e

(NO n) = λsλz(n λp(s (s p)) z)
(NI n) = λsλz(s (n λp(s (s p)) z))

(X 0) = λoλiλe(e)
(X n) = λoλiλe{(o (X (- n 1))) (i (X (- n 1)))}

(Nil 0) = E
(Nil s) = (O (Nil (- s 1)))

(One s) = (I (Nil (- s 1)))

(App 0) = λs λz z
(App n) = λs λz (s ((App (- n 1)) s z))

(Nat 0) = λs λz z
(Nat n) = λs λz ((Nat (/ n 2)) λk(s (s k)) ((App (% n 2)) s z))

(Nut bs) = (bs
  λp λs λz ((Nut p) λk(s (s k)) z)
  λp λs λz ((Nut p) λk(s (s k)) (s z))
  λs λz z)

(ID x)  = (x λx (O (ID x)) λx(I (ID x)) E)

(Is0 n) = (n λp(Is0 p) λp(λtλf(f)) λtλf(t))
(Is1 a) = (a λp(λtλf(f)) λp(Is0 p) λtλf(t))

(Inc x) = λo λi λe (x i λx(o (Inc x)) e)

(Mul3 a) = λoλiλe(a λp(o (Mul3 p)) λp(i (Inc (Mul3 p))) e)
  
(Bts s x) = ((Nat x) λx(Inc x) ((Nat s) λx(O x) E))

(Num x) = (x λx(+0(*2(Num x))) λx(+1(*2(Num x))) 0)

(Head bs) = (bs λpλx(O x) λpλx(I x) λx(x))
(Tail bs) = (bs λp(p) λp(p) E)

(All 0) = λsλz(z)
(All n) = λsλz {
     ((All (- n 1)) λx(s (s x)) z)
  (s ((All (- n 1)) λx(s (s x)) z))
}

(IsZ n) = (n λp(0) 1)

// CORRRECT BUT SLOW
// TODO: must take tail incrementally to avoid blowup
(SlowGen 0 skp n fn xs) = E
(SlowGen d skp n fn xs) = 
  let n0  = λx(n (O x))
  let n1  = λx(n (I x))
  let ctr = ((skp ((Nut (n E)) fn xs)) λpλx(O x) λpλx(I x) λx(x))
  let skp = λx(Tail (skp x))
  let x0  = (SlowGen (- d 1) skp n0 fn xs)
  let x1  = (SlowGen (- d 1) skp n1 fn xs)
  (ctr {x0 x1})

Main =
  let s = 12
  let z = (Nil s)
  let o = (Bts s 1)
  let g = (Bts s 3)
  //((Nut (I (I (I E)))) λx(+ x 1) 0)
  //(Is1 (SlowGen s λx(x) λx(x) λx(Mul3 x) o))
  ((Is1 ((All s) λx(Mul3 x) g)) 1 0)

  //(Gen 6 λx(x) λsλz(z) λsλz(s z) λx(Mul3 x) o)


  //(Is0 ((Nat 256) λx(Mul3 x) g))
  //(Is0 (λsλz({z (s {z (s z)})}) λx(Mul3 x) g))

  //((Is1 (Big 256)) 1 0)
  //((Is1 (Big 256)) 1 0)


//OK: {1 {{0 {{0 {{0 {{0 {{0 {(T) (T)}} {0 {(T) (T)}}}} {0 {{1 {(T) (T)}} {1 {(T) (T)}}}}}} {0 {{1 {{0 {(T) (T)}} {0 {(T) (T)}}}} {1 {{1 {(T) (T)}} {1 {(T) (T)}}}}}}}} {0 {{1 {{0 {{0 {(T) (T)}} {0 {(T) (T)}}}} {0 {{1 {(T) (T)}} {1 {(T) (T)}}}}}} {1 {{1 {{0 {(T) (T)}} {0 {(T) (T)}}}} {1 {{1 {(T) (T)}} {1 {(T) (T)}}}}}}}}}} {1 {{0 {{0 {{0 {{0 {(T) (T)}} {0 {(T) (T)}}}} {0 {{1 {(T) (T)}} {1 {(T) (T)}}}}}} {0 {{1 {{1 {(T) (T)}} {1 {(T) (T)}}}} {1 {{0 {(T) (T)}} {0 {(T) (T)}}}}}}}} {0 {{1 {{1 {{0 {(T) (T)}} {0 {(T) (T)}}}} {1 {{1 {(T) (T)}} {1 {(T) (T)}}}}}} {1 {{0 {{0 {(T) (T)}} {0 {(T) (T)}}}} {0 {{1 {(T) (T)}} {1 {(T) (T)}}}}}}}}}}}}
//ER: {1 {{0 {{0 {{0 {{0 {{0 {(T) (T)}} {0 {(T) (T)}}}} {0 {{1 {(T) (T)}} {1 {(T) (T)}}}}}} {0 {{1 {{0 {(T) (T)}} {0 {(T) (T)}}}} {1 {{1 {(T) (T)}} {1 {(T) (T)}}}}}}}} {0 {{1 {{0 {{0 {(T) (T)}} {0 {(T) (T)}}}} {0 {{1 {(T) (T)}} {1 {(T) (T)}}}}}} {1 {{1 {{0 {(T) (T)}} {0 {(T) (T)}}}} {1 {{1 {(T) (T)}} {1 {(T) (T)}}}}}}}}}} {1 {{0 {{0 {{0 {{0 {(T) (T)}} {0 {(T) (T)}}}} {0 {{1 {(T) (T)}} {1 {(T) (T)}}}}}} {0 {{1 {{1 {(T) (T)}} {1 {(T) (T)}}}} {1 {{0 {(T) (T)}} {0 {(T) (T)}}}}}}}} {0 {{1 {{1 {{0 {(T) (T)}} {0 {(T) (T)}}}} {1 {{1 {(T) (T)}} {1 {(T) (T)}}}}}} {1 {{0 {{0 {(T) (T)}} {0 {(T) (T)}}}} {0 {{1 {(T) (T)}} {1 {(T) (T)}}}}}}}}}}}}

// Q: can we generate the binary tree below efficiently?

//1
//10
//0000
//11001100
//11110000 11110000
//01001111 10110000 01001111 10110000
//11100101 11111111 00011010 00000000 11100101 11111111 00011010 00000000
//11111111 10001011 10011110 11011111 00000000 01110100 01100001 00100000 11111111 10001011 10011110 11011111 0000000001110100 01100001 00100000
//...

Multiples of 3:

//1
//11
//1001
//11011
//10001 0 1
//11001 1 11
//10011 0 1101
//11010 0 010001
//10000 1 0110011
//11000 1 110011001
//10010 1 0101100111
//11011 1 111100110101
//10001 1 11110110000001
//11001 0 111100101000011
//10011 1 10110111110001001
//11010 1 100100111101011011
//10000 0 10111010110000100101
//11000 0 111010000101001101111
//10010 0 10100010011110100011101
//11011 0 1111001101011000101010001
//10001 0 01110110000010101111110011
//11001 1 0101001010001111101111011001
//10011 0 00000111110010111001110010111
//11010 0 1000010111011110101101011110101
//10000 1 110001110100111000010000111000001
//11000 1 0101010100011010100110001010100011
//10010 1 111111111001000000110010111111001001
//11011 1 0111111110111000001001111011110111011
//10001 1 001111111001101000110101100111001100101
//11001 0 0110111110110000101000001011010110011111
//10011 1 010001111001010011110000111000001011011101
//11010 1 00010101101111101011010010101000111000110001
//10000 0 010111110001111000010001111111001010101001011
//11000 0 01110111010101101001100101111101111111110111001
//10010 0 010100110000001000110011110111001111111100110111
//11011 0 01111010010000110010011011001101101111110110001101
//10001 0 1101100011100010011101000101100010011111001010100001
//11001 1 10001010101010110101000101110010110101110111111100011
//10011 0 1010111111111110000001011101011110000011001111110101001
//11010 0 00000111111111101000011101000011101000100110111100000111
//10000 1 0000010111111110001001010001001010001011010001110100010101
//11000 1 10000111011111101011011110011011110011100001010100010111111
//10010 1 0010010100111110000100111011000111011010100111111001110111101
//11011 1 101101111010111010011010100101010100100000110111101101001110001
//10001 1 1001001110000110001100000011111111101100001000111001000110101011
//11001 0 101110101010010010100100001011111110010100110010101110010000000101
//10011 1 1110100000001110111101100011101111101111101001111110101110000001111
//11010 1 111000100000101001110010101010011110011110001101111000011010000101101
//10000 0 11101011000011110101011111111101011011011010100011101001000010011100001
//11000 0 101000010100101100000011111111000010010010000010101000111000110101010011
//10010 0 11110001111011100100001011111101001101101100001111110010101010000000011001
//11011 0 101101010110011011100011101111000110001001010010111101111111110000000100111
//10001 0 00010000001011000110101010011101010010110111101110110011111111010000011010101
//11001 1 0001100000111001010000000011010000011110001110011001011011111100010001000000001
//10011 0 01010010001010111110000000100001000101101010101100111100011111010110011000000011
//11010 0 1111101100111110111010000011000110011100000000010110110101011100001011001000001001
//10000 1 10111001011011100110001000100101001101010000000111000100000011010011100111000011011
//11000 1 0001101111000110110010110011011110100000010000010101011000001000011010110101001000101
//10010 1 10010001110101000101111001100011100010000110000111111100100011000100000100000111001111
//11011 1 0011100101000001011101101100101010101100010010010111110111001001011000011000010101101101
//10001 1 011010111110000111010010010111111111100101101101110111001101110111001001001001111100010001
//11001 0 0010000111101001010001110111011111111011110001001100110110001100110111011011010111010110011
//10011 1 001100010110001111100101001100111111100111010110100110001010100110001100100100001100001011001
//11010 1 0110010111001010111011111010011011111011010000100011001011111101001010011101100010010011100111
//10000 0 001011110101111110100111100011000111100100010011001001111011110001111101010010101101101010110101
//11000 0 00111011000011111000110110101001010110111001101001110101100111010101110000011111100010000001000001
//10010 0 001010010100101110101000100000111111000110110000110100001011010000001101000101111010110000011000011
//11011 0 00111101111011101000001011000010111101010001010010000100111000010000100001011101100001010001001001001
//10001 0 101011001110011000100011100100111011000001011110110001101010100110001100011101001010011110011011011011
//11001 1 11111001101011001011001010111010100101000111011001010100000000110010100101010001111101011011000100100101
//10011 0 111110110000010111100111111010000011111001010010111111100000001001111101111110010111000010010101101101111
//11010 0 01111001010001110110110111100010001011101111101110111110100000110101110011111011110101001101111100010011101
//10000 1 0101101111100101001001001110101100111010011110011001111000100010000011011011100111000001100011110101101010001
//11000 1 11110001111011111011011010100001011010001101101100110110101100110000100010011011010100010010101100001000001011
//10010 1 0111010101100111100100100000100111000010100010010110001000010110010011001101000100000101101111100100110000111001
//11011 1 11010000001011011011101100001101010100111100110111001011000111001110100110000101100001110001111011101001001010111
//10001 1 1100010000111000100110010100100000000110110110001101111001010101101000110010011100100101010101100110001110111110101
//11001 0 110101100010101011010011111011000000010001001010100011101111111100001010011101010111011111111100110010101001111000001
//10011 1 1000001010111111100001101110010100000110011011111100101001111111010011110101000000110011111111011001111111010110100011
//11010 1 101000111110111110100100011011111000010011000111110111110101111100011011000001000010011011111100101101111100001000101001
//10000 0 1000101011100111100011100100011110100110100101011100111100001111010100010100011000110100011111011110001111010011001111011
//11000 0 110011111010110110101010111001011000110000111111010110110100101100000101111001001010000101011100111010101100011001101100101
//10010 0 1001101110000100100000000110111100101001001011110000100100011110010001110110111011110001111101011010000001010100110001011111
//11011 0 110100011010011011000000010001110111110110111011010011011001011011100101001001100111010101110000100010000111111010010111011101
//10001 0 01000101000011000101000001100101001111001001100100011000101111000110111110110100110100000011010011001100010111100011110100110001
//11001 1 011001111000100101111000010011111010110111010011100100101110110101000111100100011000010000100001100110010111011010101100011001011
//10011 0 00101101101011011101101001101011100001001100011010111011101001000001010110111001001001100011000100110011110100100000010101001111001
//11010 0 101110001000010011001000110000011010011010010100000110011000111000011111000110111011010010100101101001101100011100000111111010110111
//10000 1 11101010110001101001110010010001000011000011111000010011001010101001011101010001100100011111011100001100010101010100010111100001001101
//11000 1 0110000001010100001101011101100110001001001011101001101001111111110111010000010100111001011100110100100101111111111001110110100110100001
//10010 1 11001000011111100010000011001011001011011011101000110000110111111100110001000111101010111101011000011101110111111110110100100011000010011
//11011 1 0101110001011110101100001001111001111000100110001010010010001111110110010110010110000001110000101001010011001111111001000111001001001101001
//10001 1 00001101011101100001010011010110110110101101001011110110110010111100101111001111001000010101001111011110100110111110111001010111011010000111
//11001 0 0100100000110010100111101000001001001000010001111011001001011110110111101101101101110001111110101100111000110001111001101111110100100010010101
//10011 1 01101100001001111101011000100011011011000110010110010111011101100100111001001001001101010111100001011010101001010110110001111100011100110111111
//11010 1 0010010100110101110000101011001000100101010011110011110100110010111010101110110110100000001110100111000000001111110001010101110101010110001111101
//10000 0 011101111010000011010011111001110011011111101011011011000110011110100000011001001000100000101000110101000000101111010111111101000000001010101110001
//11000 0 0101001110001000100001101110110101100011111000010010010101001101100010000100111011001100001111001000000100001110110000111111000100000011111110101011
//10010 0 011110101010110011000100011001000010101011101001101101111110100010101100011010100101100100101101110000011000101001010010111101011000001011111000000101
//11011 0 0101100000000101100101100100111000111111101000110001001111100010111110010100000011110011101110001101000100101111011110111011000010100011101110100001111

//-1 {0 1}

//-10 {0 0}
//-11 {0 0}

//-100 {0 1}
//-110 {0 1}

//-1000 {0 1}
//-1100 {0 1}
//-1001 {0 1}
//-1101 {1 0}

//-10000 {0 1}
//-11000 {0 1}
//-10010 {0 1}
//-11011 {0 1}
//-10001 {0 1}
//-11001 {1 0}
//-10011 {0 1}
//-11010 {0 1}

//(1 {
  //(0 {
    //(0 {
      //(0 {0 1})
      //(1 {0 1})
    //})
    //(0 {
      //(0 {0 1})
      //(1 {0 1})
    //})
  //})
  //(1 {
    //(0 {
      //(0 {0 1})
      //(1 {1 0})
    //})
    //(0 {
      //(0 {0 1})
      //(1 {1 0})
    //})
  //})
//})

//3^N % 2 == 1
//3^N % 4 == 

//3^N / 2 % 2

//1 1 
//4 0
//13 1
//40 0
//121 1
//364 0