Prime factorization decomposition

Posted on julio 04, 2013 by Excel Pedro Wave

Decomposition problems

If someone believes that the integer factorization is solved with a simple formula is very wrong. The algorithms that try to break down a number into its prime factors are an asset to put to work quantum computers, designed the most powerful so far. One of the best known algorithms is the Shor's algorithm.

RSA problem

The day that run Shor's algorithm on a quantum computer will be of no use secret codes to make an electronic transaction or signing a document with our electronic ID. RSA public keys will be possible to be deciphered, is known as the RSA problem in cryptography that relies on the security of not being able to find the two primes that decompose a secret key in computation polynomial time.

One doubt arises to me. U.S. intelligence agencies already have quantum computers able to decipher secret codes and to key factorially decomposing into its two prime numbers? If so, our privacy is in tatters and also our confidence in the security of our data and our private communications. The PRISM monitoring program can be finished them off, as reported in the current following links:

PRISM (surveillance program)

Skype's secret Project Chess reportedly helped NSA access customers' data

Why ‘I Have Nothing to Hide’ Is the Wrong Way to Think About Surveillance

What is at stake is to not even be authors of our own issues, if anyone can supplant us using our secret keys, or creating them instead of us (in case you believe that without using the Internet will be free of impersonation of your digital identity).

Factorial decomposition

This article does not try to break composite keys extremely long into prime numbers, but with 6 digits or up to 1,000,000, with an Excel template to serve in school or college and can be uploaded to the cloud in order to exercise ourselves in finding the prime factors anywhere with internet connection.

The factorization allows you to obtain the prime numbers with exponents, which are divisors of an integer. Eg

70776 = 2³ · 3² · 983

It agreed to use the punctuation symbol "·" as a multiplication operator prime factorization, although you can use other symbols, such as:. (decimal point), x (sign for), * (asterisk sign).

On the right is the integer factorization of 70776, as a product of prime factors: 2, 3 and 983. The number 2 is raised to the 3rd power, it is necessary to multiply three times:
2³ =2 x 2 x 2 = 8.

Prime numbers

In the above example it is easy to obtain the factors 2 and 3 as they are small numbers, but not so easy to know if 983 is prime.

Prime numbers are natural numbers (integers greater than 1) that are divisible by 1 and by themselves, and there are infinite. The set of all prime numbers is represented by the symbol: $\mathbb{P}$

One method to determine whether a composite number is prime is to try to divide it by each of the prime numbers smaller than it and, if there is none that can divide it, you can ensure it is a prime number.

There are special primes as commenting The Solitude of Prime Numbers novel, are the twin primes, which are two consecutive odd prime numbers (except 2, all prime numbers are odd) as 11 and 13, 17 and 19, or 41 and 43.

In the following links you can explore some of the known problems with prime numbers, that many headaches facing students of the number theory:

List of unsolved problems in mathematics: Number theory (prime numbers)
Twin prime conjecture

Goldbach conjecture

Prime number theorem

Riemann hypothesis

Millennium Prize Problems (US$1,000,000 prize)

Decomposition into SkyDrive cloud

Following a question from a math teacher I thought making this template in Excel 2010 that allows to practice factorization of a composite number into its prime factors from SkyDrive, without having Excel installed, thanks to solving only with formulas because macros can not be uploaded to the cloud from Microsoft Excel 2007 or 2010.

NOTE: You can edit the cell B11 and the range C11:C30, do not modify the other cells!

NOTE: To erase numbers, if backspace or delete keys not work, type a space and a backspace, so that the cell is empty.

Download template compatible with Excel 2003

Download the latest version below that allows numbers between 2 and 2,251,799,999,999
The ExcelWebApp cloud version only supports up to 1,000,000
Help with "?" character does not work in Excel 2003 for very large values.

GUESSING GAME FOR DECODERS:
A hidden character, written in cell C11, automatically calculates the prime factors of the number written on B11. Can you guess?

Download English templates for Excel 2003, 2007 and 2010 from this link:

DescomposiciónFactorial-PW5.zip

Factores sheet (factors)

Cell B11 - Enter the composite number (between 2 and 1000000).
Range C11:C30 - Enter the prime factors that decompose the previous composite number. (warns if not prime or not divide the composite number)
Cell B8 - Factorization is displayed as powers of prime numbers. (eg 234 = 2 · 3² · 13)
Cell F10 - To change the multiplier symbol of the prime factors, default "·" (eg: · x . * ).

Primos sheet (primes)

Range A2:A21 - Formula to find out if it is a prime number when it is greater than 0.
Range B2:B21 - List the prime numbers in increasing order.
Range C2:C21 - Calculate the number of repetitions of each prime.
Range D2:D21 - Gets the factorization.
Range G2:H21 - Superscripts of exponents auxiliary list to graphically represent powers of prime numbers (up to 20th).

Divisores sheet (dividers)

Range A2:A21 - Composite numbers of the range Factores!B11:B21
Range B2:B21 - Array formula to obtain the prime factors.
Range C2:C21 - Dividers of the composite numbers and their factors.
Range D2:D21 - Prime number, prime factor or less than F1 cell.
Cell F1 - For the user to find out the dividers less than this value, default: 20.

Array formula to obtain the prime factors:

{=IF(ISEVEN(A2),2,MIN(IF(MOD(A2,
ROW(INDIRECT("2:"&INT(ROUNDDOWN(SQRT(A2)+1,0)/2)))*2-1)=0,0,A2)+
ROW(INDIRECT("2:"&INT(ROUNDDOWN(SQRT(A2)+1,0)/2)))*2-1,A2))}

With this formula, by introducing the "?" character, without the quotation marks, in the range Factors!C11:C30, you can know which is the prime factor.

Formulas for identifying prime numbers

The formula to determine if a number is prime the've taken by the expert in Excel, José Ramón García, on their website:

www.jrgc.es - AVERIGUAR SI UN NÚMERO ES PRIMO USANDO UNA FÓRMULA

The following array formula (entered by pressing both keys: Ctrl + Shift + Enter) lets you know if a number is prime (result greater than 0), up to 4,295,098,367 in Excel 2003 to 1,099,513,724,928 in later versions, values sufficient for 1000 (1,000,000 square root of which is the maximum composite number in this template).

{=IF(OR(NOT(ISNUMBER(Factores!C11)),Factores!C11 < 2,ISBLANK(Factores!C11)),0,
Factores!C11*(SUM(--(FLOOR(Factores!C11,
ROW(INDIRECT("1:"&INT(SQRT(Factores!C11)))))=Factores!C11))=1))}

With the 4th formula in above link you can find out if a number is prime to 15 digits (maximum accuracy of Excel). With VBA macros can be solved for more digits with a higher computation time with a function like this:

www.jrgc.es - Función para saber si un número es primo

Prime number	Digits	Process time
535006138814359	15	00:00:18
4847464544434241	16	00:00:54
55350776431903243	17	00:03:03
496481100121144169	18	00:09:12
6082394749206781697	19	00:32:19

But this I leave to future articles on calculations with large numbers of time if we trust Edward Snowden in terms of the protection offered by encryption:
"Encryption works. Properly implemented strong crypto systems are one of the few things that you can rely on. Unfortunately, endpoint security is so terrifically weak that NSA can frequently find ways around it."

theguardian - Edward Snowden's live Q&A: eight things we learned

No Response to "Prime factorization decomposition "

Indícame las erratas que encuentres y qué es lo que te gustaría ver en los próximos artículos.

#ExcelPedroWave

Traducir el blog