Shor’s algorithm with harbour

The fields of quantum computing and artificial intelligence are developing every day without any special mention. In the future, even basic functional programming will be automated, which means that some “arrogant programmers” who rely only on functional coding will have no place.

I believe that true computer science should be fundamentally rooted in philosophy – if you don’t love people and the discipline, any academic pursuit is meaningless.

On the other hand, in the open source community, we see individuals hiding their code and rudely demanding other people’s code. It’s frustrating to see people who hide their code acting like schoolyard bullies, and I don’t want to waste my time on such low-level bullying.

With the advent of quantum computing, traditional naive encryption will be broken. How? Because of Shor’s algorithm, which is designed to factorize numbers. Here’s how it’s implemented in harbor code:

Shor’s algorithm

/*
  Shor's algorithm
  c)copyright Charles KWON ( charleskwonohjun@gmail.com )

  The following code implements Shor's algorithm using a classical CPU. 
  Once quantum computers are available, by adding QFT(Quantum Fourier Transform) to the code below, most RSA encryptions can be decrypted.
  
  https://en.wikipedia.org/wiki/Shor%27s_algorithm
  
*/

FUNCTION Main()
   LOCAL N := 38 // For example purposes
   LOCAL aResult

   aResult := factorizeByShor(N)

   ? "Factor 1:", aResult[1]
   ? "Factor 2:", aResult[2]

RETURN NIL

FUNCTION mod_pow(a, x, N)
   LOCAL y := 1

   WHILE x > 0
      IF BitAnd(x, 1) <> 0
         y := y * a % N
      ENDIF

      x := ShiftRight(x, 1)
      a := a * a % N
   ENDDO

RETURN y

FUNCTION findPeriodByModPow(N, a)
   LOCAL x

   FOR x := 1 TO N - 1
      IF (mod_pow(a, x, N) == 1)
         RETURN x
      ENDIF
   NEXT

RETURN -1

FUNCTION factorizeByShor(N)
   LOCAL a, gcd, r, gcd1, gcd2

   IF mod(N, 2) == 0                         // speed optimize ,  CharlesKWON
      RETURN { 2, N / 2}
   ENDIF

   WHILE .T.
      a := RandomRange(2, N)
      gcd := GCD(N, a)

      IF (gcd != 1)
         RETURN {gcd, N / gcd}
      ENDIF

      r := findPeriodByModPow(N, a)

      IF (r % 2 != 0)
         LOOP
      ENDIF

      gcd1 := GCD(N, Pow(a, r / 2) + 1)
      gcd2 := GCD(N, Pow(a, r / 2) - 1)

      IF (gcd1 == 1 .OR. gcd2 == 1)
         LOOP
      ENDIF

      RETURN {gcd1, gcd2}
   ENDDO

RETURN NIL

/*
   Greatest Common Divisor (GCD)
*/
FUNCTION GCD(a, b)
   LOCAL temp

   WHILE b != 0
      temp := a
      a := b
      b := temp % b
   ENDDO

RETURN a

FUNCTION RandomRange(nLower, nUpper)
RETURN nLower + INT(RAND() * (nUpper - nLower + 1))

FUNCTION ShiftRight(nValue, nShift)
RETURN nValue / (2 ^ nShift)

FUNCTION BitAnd(a, b)
   LOCAL nRet := 0

   IF a <> 0 .AND. b <> 0
      nRet := 1
   ENDIF

RETURN nRet

I’ve implemented it using a traditional CPU-based algorithm, as shown in the figure above. Pretty easy to understand, right?

Add quantum code to the mix and all existing RSA encryption would be broken in a heartbeat. Once again, true computer science must be grounded in the philosophy that underlies the science.

Simply knowing how to write a few lines of basic code and being satisfied with the status quo will not save you. With the advent of AI and quantum computing, these school bully types will become obsolete.

Good luck.