Home » Security Bloggers Network » The Block Factorization Algorithm

The Block Factorization Algorithm

by Jason on November 17, 2013

Here is a simple semiprime (N=p*q) factorization algorithm with running time O((p-q)/2). It is based on the concept of N (p*q) unit blocks being arranged into a perfect rectangle. The rectangle has rows and columns. At the beginning of the algorithm, the rectangle’s width and height are initialized to ~ sqrt(N). Blocks that can’t fit are placed on a heap. In each iteration, the algorithm removes 2 columns and places them on the heap or takes blocks from the heap to make two rows. The algorithm terminates when the number of blocks on the heap is zero.

In action:

./blockfact-simple.py 518912618149
init rounds 0 a 720355 b 720355 heap 1292124
n 518912618149 rounds 60774 a 662141 b 783689 heap 0

Now the code:

#! /usr/bin/env python
# The Block Method of Integer Factorization
# Jason Royes, 2013
#
# This simple algorithm finds primes p, q where N = p*q
# and runs in approximately O((p – q) / 2) time

from gmpy import sqrt
import sys

class BlockFactorization:

def init_shape_square(self, blocks):
self.a = (sqrt(blocks) – 1) | 1
self.b = self.a
self.heap = blocks – (self.a * self.b)
self.blocks = blocks
self.rounds = 0

def __str__(self):
return “rounds %d a %d b %d heap %d” %(self.rounds, self.a, self.b, self.heap)

def add_rows(self, rows=2):
need = rows * self.a
if self.heap >= need:
# add rows from heap
self.heap -= need
self.b += rows
else:
# take from columns, put on heap
self.heap += (rows * self.b)
self.a -= rows

def factor(self):
self.rounds = 0

while self.heap != 0:
self.add_rows()
self.rounds += 1

if __name__ == “__main__”:
n = int(sys.argv[1])
bf = BlockFactorization()
bf.init_shape_square(n)
print “init”, bf
bf.factor()
print “n”, n, bf