RSA factorisation demo

'RSA factorisation demo
'---------------------------

'let's make some primes
DIM pr(4000) AS LONG
pr(0) = 2: N = 3:: jmax = 0: i = 0
WHILE i < 4000
  IF pr(jmax) * pr(jmax) < N THEN jmax = jmax + 1
  ok = 1
  FOR j = 0 TO jmax
    IF N MOD pr(j) = 0 THEN ok = 0: j = jmax
  NEXT
  IF ok = 1 THEN i = i + 1: pr(i) = N
  N = N + 2
WEND
RANDOMIZE TIMER

'let's make some coprime semiprimes
DIM sp(7) AS LONG
FOR i = 0 TO 7
  sp(i) = pr(i) * pr(16 - i)
NEXT

'and let's make two of these share a common factor, as might happen if the prime generating RNG has some bias.
i = INT(RND * 8): j = INT(RND * 7): IF j >= i THEN j = j + 1
k = INT(RND * 16 + 16)
sp(i) = pr(i) * pr(k)
sp(j) = pr(j) * pr(k)
PRINT "Our semiprimes:"
FOR i = 0 TO 7: PRINT sp(i);: NEXT: PRINT

DIM bitmask AS LONG, Q0 AS _UNSIGNED _INTEGER64, Q1 AS _UNSIGNED _INTEGER64, Q AS _UNSIGNED _INTEGER64
'Need to make all these variables 'bigints' for this to be more impressive... This is a very simple demo.

'Partition S into two half sets S0 and S1, via Hadamard basis vectors.
'Q0 and Q1 are each the product of elements in the corresponding half set.
'We need only log2(8)=3 gcd tests for these 8 semiprimes. So k runs from 0 to 2.

'In proper tests, we might have millions of keys scraped from web traffic.
'If some are generated with bad RNGs, then there could be common prime factors
'among them, which could be found with this algorithm, to factorise those keys.

PRINT "Search for common factors:"
FOR k = 0 TO 2: bitmask = 2 ^ k
  Q0 = 1: Q1 = 1
  FOR i = 0 TO 7
    IF (i AND bitmask) > 0 THEN Q0 = Q0 * sp(i) ELSE Q1 = Q1 * sp(i)
  NEXT
  'Find Q = GCD(Q0,Q1)
  IF Q0 < Q1 THEN Q = Q0: Q0 = Q1: Q1 = Q
  WHILE Q0 > 0
    Q = Q0: Q0 = Q1 MOD Q0: Q1 = Q
  WEND
  Q = Q1
  IF Q > 1 THEN PRINT Q 'if we find a common prime, show it.
NEXT