Semiprimes

Between 1991 and 2007, RSA laboratories were awarding cash prizes to any individual who could factor any number from their published list of semiprimes known as RSA numbers.  The first cash prize of $1000 was given on April 1, 1991 to Arjen Lenstra for factoring RSA-100, a semiprime with 100 decimal digits (330 binary digits), and the largest cash prize of $20,000 was given on November 2, 2005 to Jens Franke for factoring RSA-640, a semiprime with 193 decimal digits (640 binary digits).  To date, the largest RSA number to be factored is RSA-220, a semiprime with 220 decimal digits (729 binary digits) on May 13, 2016, but unfortunately no cash prize was given since the challenge is now over.

A semiprime is the product of two prime numbers.  For example, 15 is a semiprime because it is the product of the two primes 3 and 5.  The RSA Challenge is to find the two prime factors when given just the semiprime.  There are several ways to do this, but all of them are time consuming for large numbers.

Factoring Methods

For example, let’s say you wanted to find the two prime factors of the semiprime 91.  One way would be to divide 91 by each prime number between 1 and the square root of 91 until you reach one that divides it evenly.  So in this case, 91 ÷ 2 = 45 r 1 (no), 91 ÷ 3 = 30 r 1 (no), 91 ÷ 5 = 18 r 1 (no), 91 ÷ 7 = 13 r 0 (yes!), so 91 = 7 x 13.  (This method can be made to go somewhat faster by using divisibility rules.)

Another way would be to subtract a perfect prime square and see if the difference is also divisible by that squared number.  This is because if you call the semiprime n and the two factors p and p + d, n = p(p + d) or n = p² + pd or n – p² = pd.  So to factor 91, (91 – 2²) ÷ 2 = 43 r 1 (no), (91 – 3²) ÷ 3 = 27 r 1 (no), (91 – 5²) ÷ 5 = 13 r 1 (no), (91 – 7²) ÷ 7 = 6 r 0 (yes!), so 91 is divisible by 7.

One more way to factor a semiprime would be to add a perfect square and see if the sum is also a perfect square (assuming the semiprime is odd).  This is because if you call the semiprime n and the two factors p and q, and let u = ½(p + q) and v = ½(q – p), then u – v = ½(p + q) – ½(q – p) = ½p + ½q – ½q + ½p = p and u + v = ½(p + q) + ½(q – p) = ½p + ½q + ½q – ½p = q, which means n = pq = (u – v)(u + v) = u² – v², or n + v² = u².  So to factor 91, 91 + 1² = 92 (not a square), 91 + 2² = 95 (not a square), 91 + 3² = 100 = 10² (a square!), so the two factors of 91 are 10 – 3 and 10 + 3, or 7 and 13.  (This method can be made to go somewhat faster by filtering out sums whose last digit cannot possibly be a square number, which include 2, 3, 7, and 8.)

Computer Encryptions

As mentioned earlier, all the methods for factoring a large semiprime are time consuming, even for a computer, because they all use some variation of brute force or trial and error.  Computer programs rely on this fact with public and private key encryptions.  In a computer encryption, each user is given a public key (a large semiprime typically 1024 or 2048 binary digits long) that is publicly available for others to use to encode a message.  The message can then be decoded only by the private key (the two factors of the semiprime) that is known only by the receiver.  The RSA Challenge (hopefully) proved that this method of encryption is safe, because even after over 25 years nobody come even close to factoring RSA-1024.

Unfortunately, just like World War 2 Germany, public and private key computer encryptions are fighting a two-front war.  On the one front is mathematics – someone in the future may be clever enough to think of a more efficient way to factor large semiprimes.  On the other front is technology – someone in the future may develop a computer fast enough to use a brute force method to be able to factor large semiprimes.

Either way, the first person who can successfully factor large semiprimes, whether it is by a mathematical or technological breakthrough, would have the power to hack into anybody’s computer and steal their identity, including their bank account and credit card information, which presents an interesting hypothetical dilemma.  If this were to happen, will he or she use it for good or for evil? If for good, will he or she give large companies sufficient warning to find a new computer encryption method?  In the time in between, will he or she be kidnapped by the bad guys and forced to hack into computers for them?  Sounds like a Hollywood movie in the making!

At any rate, like all two-front wars it will only be a matter of time before the middle man will be defeated.  At some point, public and private key computer encryptions will become obsolete. Already on the technology front quantum computer processors are being developed where if they work they could factor large semiprimes almost instantaneously.  It’s time for a new encryption method!

Using Your Computer to Calculate Pi

On March 21, 2015, Rajveer Meena recited 70,000 digits of pi from memory in just under 10 hours in Vellore, India, for the Guinness World Record of most digits of pi memorized.  Apart from utter amazement by this feat of memory, have you ever wondered how mathematicians can even calculate such a long list numbers for pi?

There are actually several methods for calculating pi.  You might recall from your math classes that pi is the ratio between the circumference and diameter of any circle, and so one way to calculate pi is to construct a circle, directly measure its circumference and diameter, and divide the two.  Unfortunately, this is only precise enough to obtain a few decimal places of pi.  Another way to calculate pi is to find the perimeter or areas of inscribed or circumscribed polygons of circles.  This was the technique favored by mathematicians before the invention of calculators and computers, but its precision is still limited to “just” a few hundred digits of pi.

inscribed octagon

Today, computers can be used to calculate millions of digits of pi by using infinite series formulas.  There are several different ways to do this, but one of the most efficient methods that is relatively straightforward is to combine Machin’s formula:

with the arc-cotangent power series formula:

The computer program for this is as follows:

01	# Pi Calculator
02	# Python 2.7.3
03	# After running, type "pi(n)" where n is the number of decimals for pi.  For
04	#  example, if you would like to calculate 100 decimals for pi, type "pi(100)".
05
06	# import python libraries
07	from decimal import Decimal, getcontext
08	from time import time, strftime
09	import datetime
10
11	# arccot function using power formula arccot = 1/x - 1/(3x^3) + 1/(5x^5) ...
12	def arccot(x, digits):
13	# set precision and starting values
14	getcontext().prec = digits
15	total = 0
16	n = 1
17	# loop while new term is large enough to actually change the total
18	while Decimal((2 * n - 1) * x ** (2 * n - 1)) < Decimal(10 ** digits):
19	# find value of new term
20	term = ((-1)**(n - 1)) * 1 / Decimal((2 * n - 1) * x ** (2 * n - 1))
21	# add the new term to the total
22	total += term
23	# next n
24	n += 1
25	# return the sum
26	return total
27
28	# pi function
29	def pi(decimals):
30	# start timer
31	timestart = time()
32
33	# find pi using Machin's Formula pi = 4 * (4 * arccot(5) - arccot(239))
34	#  and the power formula for arccot (see arccot function above)
35	print "pi = " + str(Decimal(4 * (4 * arccot(5, decimals + 3) - arccot(239,
36	decimals + 3))).quantize(Decimal(10) ** (-decimals)))
37
38	# display elapsed time
39	timeelapsedint = round(time() - timestart, 2)
40	timeelapsedstr = str(datetime.timedelta(seconds = round(
41	timeelapsedint, 0)))
42	print "runtime: " + timeelapsedstr + " or " + str(
43	timeelapsedint) + " seconds."

Here’s what happens when you use the program to find the first 1,000 decimal places for pi on a dual-core 1.67 GHz processor (a mediocre-speed laptop for 2016):

>> pi(1000) pi = 3.14159265358979323846264338327950288419716939937510 582097494459230781640628620899862803482534211706798214808 651328230664709384460955058223172535940812848111745028410 270193852110555964462294895493038196442881097566593344612 847564823378678316527120190914564856692346034861045432664 821339360726024914127372458700660631558817488152092096282 925409171536436789259036001133053054882046652138414695194 151160943305727036575959195309218611738193261179310511854 807446237996274956735188575272489122793818301194912983367 336244065664308602139494639522473719070217986094370277053 921717629317675238467481846766940513200056812714526356082 778577134275778960917363717872146844090122495343014654958 537105079227968925892354201995611212902196086403441815981 362977477130996051870721134999999837297804995105973173281 609631859502445945534690830264252230825334468503526193118 817101000313783875288658753320838142061717766914730359825 349042875546873115956286388235378759375195778185778053217 12268066130019278766111959092164201989 runtime: 0:00:04 or 3.73 seconds.

  

So with less than 50 lines of code, you can have your computer calculate 1,000 decimal places of pi in less than 4 seconds!  At this rate, you will have 1,000,000 decimal places of pi in just over an hour!  Not bad, considering the very first computer, the ENIAC, took 70 hours to calculate pi to 2,037 decimal places in 1949.  Computers have come a long way since then!

With better computers and more efficient (but more complicated) infinite series formulas, pi has been calculated to over 13.3 trillion digits!  This number is unfathomable to most of us.  If you were to recite this many digits of pi at the same speed as the 2015 world record holder Meena (about 2 digits per second), it would take you over 200,000 years to finish!  So why bother to find so many digits of pi?   Most mathematicians will give the same reason that mountain climbers use for climbing Mount Everest: because it’s there.

Column Division – An Alternative to Long Division

Many people have bad memories of long division.  It’s one of the first algorithms a young student learns in math class that contains multiple steps that all build on each other, so one miscalculation at the beginning can throw the whole answer off.  It also uses a combination of different operations, including division, multiplication, and subtraction, which makes it difficult to complete most problems mentally.

		1	5	4	R:2
8	1	2	3	4
		8
		4	3
		4	0
			3	4
			3	2
				2

1,234 ÷ 8 = 154 R:2

Column division is an alternative to long division, and is inspired by a specific case of synthetic division in which x is a power of 10.  The algorithm for column division is to subtract once in the beginning, and then alternate between adding and multiplying. 

Example of Column Division

For example, to divide 8 into 1,234, start by placing the 8 and 1,234 as follows:

8		1
		2
		3
		4

Subtract 10 – 8 = 2 and place it beside the 8.  This 2 will be the multiplier:

8	2	1
		2
		3
		4

Now alternate between adding and multiplying.  First, “add” 1 + 0 = 1 and place it in the second section.  Add two dashes behind the 1 (the first row will always have 2 less dashes than the number of digits in the dividend, and 4 – 2 = 2.)

8	2	1		1	_	_
		2
		3
		4

Multiply 2 · 1 = 2 and place it in the second row of the first section (beside the 2):

8	2	1		1	_	_
		2	2
		3
		4

Add 2 + 2 = 4, and place it in the second row of the second section, and add one less dash than the row above it:

8	2	1		1	_	_
		2	2		4	_
		3
		4

Multiply 2 · 4 = 8 and place it in the third row of the first section (beside the 3):

8	2	1		1	_	_
		2	2		4	_
		3	8
		4

Add 3 + 8 = 11, and place it in the third row of the second section, and add one less dash than the row above it (so no dashes):

8	2	1		1	_	_
		2	2		4	_
		3	8		1	1
		4

Multiply 2 · 11 = 22 and place it in the fourth row of the first section (beside the 4):

8	2	1		1	_	_
		2	2		4	_
		3	8		1	1
		4	22

Add 4 + 22 = 26, and since we ran out of room with the dashes, this represents a remainder, so place it in the third row of the third section:

8	2	1		1	_	_
		2	2		4	_
		3	8		1	1	26
		4	22

Since the divisor 8 divides into the remainder 26 at least 3 times, place the 3 in the fourth row of the second section, and place 8 · 3 = 24 in the fourth row of the third section:

8	2	1		1	_	_
		2	2		4	_
		3	8		1	1	26
		4	22			3	24

Subtract the numbers in the last column:

8	2	1		1	_	_
		2	2		4	_
		3	8		1	1	26
		4	22			3	24
							2

Add the numbers in the second to last column:

8	2	1		1	_	_
		2	2		4	_
		3	8		1	1	26
		4	22			3	24
				1	5	4	2

The answer can be read from the bottom row:

8	2	1		1	_	_
		2	2		4	_
		3	8		1	1	26
		4	22			3	24
				1	5	4	2

Therefore, 1,234 ÷ 8 = 154 R:2.

Example of Column Division with a Large Remainder

Sometimes the remainder is too large to divide easily, in which case you can repeat the process of column division underneath the problem with the remainder as the new divisor.  For example, to divide 7 into 12,345, start by placing the 7 and 12,345 as follows:

7		1
		2
		3
		4
		5

Subtract 10 – 7 = 3 and place it beside the 8.  This 3 will be the multiplier:

7	3	1
		2
		3
		4
		5

Now alternate between adding and multiplying.  First, “add” 1 + 0 = 1 and place it in the second section.  Add three dashes behind the 1 (the first row will always have 2 less dashes than the number of digits in the dividend, and 5 – 2 = 3.)

7	3	1		1	_	_	_
		2
		3
		4
		5

Multiply 3 · 1 = 3 and place it in the second row of the first section (beside the 2):

7	3	1		1	_	_	_
		2	3
		3
		4
		5

Add 2 + 3 = 5, and place it in the second row of the second section, and add one less dash than the row above it:

7	3	1		1	_	_	_
		2	3		5	_	_
		3
		4
		5

Multiply 3 · 5 = 15 and place it in the third row of the first section (beside the 3):

7	3	1		1	_	_	_
		2	3		5	_	_
		3	15
		4
		5

Add 3 + 15 = 18, and place it in the third row of the second section, and add one less dash than the row above it:

7	3	1		1	_	_	_
		2	3		5	_	_
		3	15		1	8	_
		4
		5

Multiply 3 · 18 = 54 and place it in the fourth row of the first section (beside the 4):

7	3	1		1	_	_	_
		2	3		5	_	_
		3	15		1	8	_
		4	54
		5

Add 4 + 54 = 58, and place it in the fourth row of the second section, and add one less dash than the row above it (so no dashes):

7	3	1		1	_	_	_
		2	3		5	_	_
		3	15		1	8	_
		4	54			5	8
		5

Multiply 3 · 58 = 174 and place it in the fifth row of the first section (beside the 5):

7	3	1		1	_	_	_
		2	3		5	_	_
		3	15		1	8	_
		4	54			5	8
		5	174

Add 5 + 174 = 179, and since we ran out of room with the dashes, this represents a remainder, so place it in the fourth row of the third section:

7	3	1		1	_	_	_
		2	3		5	_	_
		3	15		1	8	_
		4	54			5	8	179
		5	174

Since the remainder 179 is too large to divide easily into 7, repeat the process of column division by placing it as the new divisor underneath the problem:

7	3	1		1	_	_	_
		2	3		5	_	_
		3	15		1	8	_
		4	54			5	8	179
		5	174
		1
		7
		9

Once again, alternate between adding and multiplying.  First, “add” 1 + 0 = 1 and place it in the second section.  This time add one dash behind the 1 (the first row will always have 2 less dashes than the number of digits in the dividend, which now has 3 digits, and 3 – 2 = 1.)

7	3	1		1	_	_	_
		2	3		5	_	_
		3	15		1	8	_
		4	54			5	8	179
		5	174
		1				1	_
		7
		9

Multiply 3 · 1 = 3 and place it in the first section (beside the 7):

7	3	1		1	_	_	_
		2	3		5	_	_
		3	15		1	8	_
		4	54			5	8	179
		5	174
		1				1	_
		7	3
		9

Add 7 + 3 = 10, and place it in the second section, and add one less dash than the row above it (so no dashes):

7	3	1		1	_	_	_
		2	3		5	_	_
		3	15		1	8	_
		4	54			5	8	179
		5	174
		1				1	_
		7	3			1	0
		9

Multiply 3 · 10 = 30 and place it in the first section (beside the 7):

7	3	1		1	_	_	_
		2	3		5	_	_
		3	15		1	8	_
		4	54			5	8	179
		5	174
		1				1	_
		7	3			1	0
		9	30

Add 9 + 30 = 39, and since we ran out of room with the dashes, this represents a remainder, so place it in the third section:

7	3	1		1	_	_	_
		2	3		5	_	_
		3	15		1	8	_
		4	54			5	8	179
		5	174
		1				1	_
		7	3			1	0	39
		9	30

Since the divisor 7 divides into the remainder 39 at least 5 times, place the 5 in the the second section, and place 7 · 5 = 35 in the third section:

7	3	1		1	_	_	_
		2	3		5	_	_
		3	15		1	8	_
		4	54			5	8	179
		5	174
		1				1	_
		7	3			1	0	39
		9	30				5	35

Subtract the numbers in the last column:

7	3	1		1	_	_	_
		2	3		5	_	_
		3	15		1	8	_
		4	54			5	8	179
		5	174
		1				1	_
		7	3			1	0	39
		9	30				5	35
								4

Add the numbers in the second to last column:

7	3	1		1	_	_	_
		2	3		5	_	_
		3	15		1	8	_
		4	54			5	8	179
		5	174
		1				1	_
		7	3			1	0	39
		9	30				5	35
				1	7	6	3	4

The answer can be read from the bottom row:

7	3	1		1	_	_	_
		2	3		5	_	_
		3	15		1	8	_
		4	54			5	8	179
		5	174
		1				1	_
		7	3			1	0	39
		9	30				5	35
				1	7	6	3	4

Therefore, 12,345 ÷ 7 = 1,763 R:4.

Example of Column Division with a Multiple Digit Divisor

Column division can also be adjusted to handle multiple digit divisors.  If the divisor has n digits, then we can group our numbers in sets of n digits, and we can subtract the divisor from 10ⁿ to obtain the multiplier.  For example, if we were to divide 99 into 12,345, the divisor 99 has 2 digits, so we would group our numbers in sets of 2 digits each:

99		1
		23
		45

Subtract 10² – 99 = 1 and place it beside the 99.  This 1 will be the multiplier:

99	1	1
		23
		45

Now alternate between adding and multiplying.  First, “add” 1 + 0 = 1 and place it in the second section.  Add one set of two dashes behind the 1 (the first row will always have 2 less groups of dashes than the number of groups of digits in the dividend, and 3 – 2 = 1.)

99	1	1		1	_ _
		23
		45

Multiply 1 · 1 = 1 and place it in the second row of the first section (beside the 23):

99	1	1		1	_ _
		23	1
		45

Add 23 + 1 = 24, and place it in the second row of the second section, and add one less groups of dashes than the row above it (so no dashes):

99	1	1		1	_ _
		23	1		24
		45

Multiply 1 · 24 = 24 and place it in the third row of the first section (beside the 45):

99	1	1		1	_ _
		23	1		24
		45	24

Add 45 + 24 = 69, and since we ran out of room with the dashes, this represents a remainder, so place it in the second row of the third section:

99	1	1		1	_ _
		23	1		24	69
		45	24

Since the divisor 99 divides into the remainder 0 times, place 0 in the third row of the second section, and place 99 · 0 = 0 in the third row of the third section:

99	1	1		1	_ _
		23	1		24	69
		45	24		0	0

Subtract the numbers in the last column:

99	1	1		1	_ _
		23	1		24	69
		45	24		0	0
						69

Add the numbers in the second to last column:

99	1	1		1	_ _
		23	1		24	69
		45	24		0	0
				1	24	69

The answer can be read from the bottom row:

99	1	1		1	_ _
		23	1		24	69
		45	24		0	0
				1	24	69

Therefore, 12,345 ÷ 99 = 124 R:69.

Proof

The proof involves running variables through the algorithm of column division and showing that the product of the divisor and the quotient simplifies to the dividend.  Let the divisor be p with m digits, and the dividend be d₁(10^m)^{n – 1} + d₂(10^m)^{n – 2} + d₃(10^m)^{n – 3} + … + d_{n – 1}(10^m)¹ + d_n(10^m)⁰.  (So if the divisor has one digit, then m = 1 and the d variables would represent each digit in the dividend).  Then x = 10^m – p  and column division with these variables would look as follows:

p	x	d1		(d1)(10m)n–2
		d2	d1x	(d1x + d2)(10m)n–3
		d3	d1x2 + d2x	(d1x2 + d2x + d3)(10m)n–4
		…	…	…
		dn–1	d1xn–2 + d2xn–3 + d3xn–4 … dn–2x	(d1xn–2 + d2xn–3 + d3xn–4 … dn–2x + dn–1)(10m)0	d1xn–1 + d2xn–2 + d3xn–3 … dn–2x2 + dn–1x + dn
		dn	d1xn–1 + d2xn–2 + d3xn–3 … dn–2x2 + dn–1x	0	0
				d1(10m)n–2 + (d1x + d2)(10m)n–3 + (d1x2 +d2x +d3)(10m)n–4 + … + (d1xn–2 + d2xn–3 + d3xn–4 … dn–2x + dn–1)(10m)0	d1xn–1 + d2xn–2 + d3xn–3 … dn–2x2 + dn–1x + dn

The product of the divisor and the quotient then simplifies to:

p · [d1(10m)n–2 + (d1x + d2)(10m)n–3 + (d1x2 + d2x + d3)(10m)n–4 + … + (d1xn–2 + d2xn–3 + d3xn–4 … dn–2x + dn–1)(10m)0 + (d1xn–1 + d2xn–2 + d3xn–3 … dn–2x2 + dn–1x + dn)/p]	(divisor times the quotient)
d1p(10m)n–2 + (d1x + d2)p(10m)n–3 + (d1x2 + d2x + d3)p(10m)n–4 + … + (d1xn–2 + d2xn–3 + d3xn–4 … dn–2x + dn–1)p(10m)0 + (d1xn–1 + d2xn–2 + d3xn–3 … dn–2x2 + dn–1x + dn)]	(distribute p)
d1{p[(10m)n–2 + x(10m)n–3 + x2(10m)n–4 + … + xn–2(10m)0] + xn–1} + d2{p[(10m)n–3 + x(10m)n–4 … + xn–3(10m)0] + xn–2} + d3{p[(10m)n–4 + … + xn–4(10m)0] + xn–3} + … + dn–2{p[ … x(10m)0] + x2} + … dn–1{p[ … (10m)0] + x} + … dn	(rearrange and factor according to d)
d1{[10m – x][(10m)n–2 + x(10m)n–3 + x2(10m)n–4 + … + xn–2(10m)0] + xn–1} + d2{[10m – x][(10m)n–3 + x(10m)n–4 … + xn–3(10m)0] + xn–2} + d3{[10m – x][(10m)n–4 + … + xn–4(10m)0] + xn–3} + … + dn–2{[10m – x][ … x(10m)0] + x2} + … dn–1{[10m – x][ … (10m)0] + x} + … dn	(substitute p = 10m – x)
d1{[(10m)n–1 – xn–1] + xn–1} + d2{[(10m)n–2 – xn–2] + xn–2} + d3{[(10m)n–3 – xn–3] + xn–3} + … + dn–2{[(10m)2 – x2] + x2} + … dn–1{[(10m)1 – x1] + x} + … dn(10m)0	(simplify using the difference of powers equations)
d1(10m)n–1 + d2(10m)n–2 + d3(10m)n–3 + … + dn–2(10m)2 + dn–1(10m)1 + dn(10m)0	(simplify)

which is the dividend.

Assessment

With the above examples, it may seem that column division is far superior to long division because it is quicker and easier to use.  Unfortunately, this is not always true.  For example, dividing 2 into 888, which is obviously 444 by long division, would require 14 iterations of column division before obtaining a remainder smaller than 2 · 10 = 20 to complete the problem:

2	8	8		8	_
		8	64	7	2	584
		8	576
		5		5	_
		8	40	4	8	388
		4	384
		3		3	_
		8	24	3	2	264
		8	256
		2		2	_
		6	16	2	2	180
		4	176
		1		1	_
		8	8	1	6	128
		0	128
		1		1	_
		2	8	1	0	88
		8	80
		8			8	72
		8	64
		7			7	58
		2	56
		5			5	48
		8	40
		4			4	40
		8	32
		4			4	32
		0	32
		3			3	26
		2	24
		2			2	22
		6	16
		2			2	18
		2	16		9	18
				44	4	0

As a general rule of thumb, the closer the divisor is to a power of ten, the easier it is to do column division, but the further away the divisor is from a power of ten, the harder it is to do column division.  So it is easier to divide by 8 (or 9, 98, or 99, etc.) by column division than it is by long division, but it is more difficult to divide by 2 (or 3, 4, 11, or 12, etc.) by column division than it is by long division.  However, column division still remains a fascinating alternative to long division, especially since the algorithms are so completely different.