### Prime factorization decomposition

Posted on jueves, julio 04, 2013 by 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:

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:

## 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.

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?

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:

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:
 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."

#### No Response to "Prime factorization decomposition "

Dime si te gusta lo que lees y, si no te gusta, dime por qué. Tengo habilitada la moderación de comentarios. Tu comentario se publicará pronto.

Tell me if you like what you read here and if you don't like, tell me why. I've enabled comment moderation. Your comment will be published ASAP.

## Mi Lista de Blogs- My Blog List

• - Title Problema Deseamos controlar el orden en el que se apilan las barras de un diagrama de barras en ggplot2. - Gráfico originalPor defecto las barra...
Hace 9 horas
• - Cooooool
Hace 11 horas
• - Descubre Excel Online (anteriormente Excel Web App), lleva la experiencia de Microsoft Excel al explorador web, para trabajar con libros directamente en ...
Hace 18 horas
• - How to realize an alternative Design of Bullet Graphs in Tableau
Hace 19 horas
• - Hoy nos llega un juego muy entretenido de Princesa Círculo, del latin circus, significa redondez. Y aunque hay varias acepciones para el término, en este c...
Hace 22 horas
• - Leo en Magonia que un artículo ha puesto en entredicho los estudios de género y las revistas donde se publican (El pene es el causante del cambio climático...
Hace 1 día
• - Un lector del blog consultaba por la *forma de extraer información a partir de las partes que componen una fórmula*. El comentario del usuario: [...]Se tra...
Hace 1 día
• - Macro Restaurador de constancias de declaracion – PDT 621 IGV y renta: A más de uno le habrá sucedido que perdió o no logró ubicar las constancias de decla...
Hace 1 día
• - [image: Tip: How to generate random values] In this video, we'll look at a few ways to generate random values with the RANDBETWEEN function. The RANDBETW...
Hace 1 día
• - Are you every strapped for cash soon after you get your paycheck? The free Household Expense Budget is here to make sure you keep the flow of your money ...
Hace 1 día
• -
Hace 2 días
• - La segmentación de datos es una función en Excel 2016 que proporciona una manera fácil de filtrar datos de una tabla dinámica o grafico dinamico. La segmen...
Hace 3 días
• - En mi cuenta de Twitter, @connumeros, publiqué el 6/4/17 la siguiente identidad, que mi hijo Juan Luis, @juanlroldan, calificó de *anagramática*: 6417=467...
Hace 5 días
• - Soy cinturón blanco de Hive pero aprovecho el blog para mostraros como he añadido unas variables a mi consulta de Hive, en realidad espero que algún alma c...
Hace 5 días
• - To make it easy to filter for several different items, you can create a list of those items on a worksheet. Then, filter your data based on that list, so...
Hace 6 días
• - If you were around in the ‘70s, you probably remember the hard-edged, bald-headed TV police detective named Kojak. He had a signature phrase—“Who loves you...
Hace 6 días
• - VLOOKUP versus INDEX MATCH! Which is Better?[image: vlookup and index match] Chris Chau of Defeatexcel.com asked twenty-seven (27) Excel MVPs and communit...
Hace 1 semana
• - Hi friends & readers of Chandoo.org, *A quick announcement for you*. Only few hours left to 50 ways to analyze your data course … [image: 50 Ways to analyz...
Hace 1 semana
• - As posted on my blog yesterday. At a former client, I was asked to submit monthly reports that show details of work performed in 15 minute increments. My l...
Hace 1 semana
• - I have updated my Access Backup utility so it now also orks on 64 bit Access.
Hace 2 semanas
• - In February 2016 I posted a spreadsheet with examples of linking to the Python Matplotlib library with xlwings. Since then updates to xlwings required som...
Hace 2 semanas
• - Entrada núm: 6 of 6 de la serie Formas e imágenesInsertar imagen en una forma En la zona de comentarios correspondientes al video VBA para insertar imáge...
Hace 3 semanas
• - La más grande del Mundo El pasado día 7 ha abierto en Madrid la mayor tienda de la enseña ZARA en el mundo. Pese a la gran repercusión que ha tenido en...
Hace 4 semanas
• - La principal dificultad del usuario Excel experimentado al comenzar a trabajar con Power Query no es tanto acostumbrarse al nuevo entorno, comprender los n...
Hace 1 mes
• - Regular readers and clients will know that I'm a big fan of PivotTables. If you format your data into a table format, you can create all sorts of reports q...
Hace 1 mes
• - *1. Plantilla Formulario Renta 110 y Formato 1732* Presentamos Formulario Renta Actualizado 110 Persona Jurídica vinculado al Formato 1732 para Declaración...
Hace 1 mes
• - April Fools is coming up, but it falls on a weekend. So instead a post about pranking your co-workers, I thought I’d give you guys a fun way to spend your ...
Hace 1 mes
• - I’ve finally finished a demo version of Peltier Tech Charts for Excel 3.0. This trial version will allow potential users to try the software before they ...
Hace 2 meses
• - I’ve finally finished a demo version of Peltier Tech Charts for Excel 3.0. This trial version will allow potential users to try the software before they ...
Hace 2 meses
• - If you’re one of the millions of people who uses Blogger to share your views on current affairs, teach the world how to make sushi, or just offer a peek in...
Hace 2 meses
• - This Excel VBA tutorial explains how to set print area, page width, Print Title, Orientation in Excel VBA. Excel VBA set print area To set Print Area in ...
Hace 2 meses
• - This post summarizes a few key points in my NTTS2017 effective data visualization for statistical offices The original post is titled A companion post to...
Hace 2 meses
• - […] La entrada Cómo insertar y mover libremente etiquetas de datos en cualquier gráfico de Calc aparece primero en Funcionarioseficientes.
Hace 2 meses
• - I've been using a Chromebook for a few years now, and find myself going for long stretches without needing to turn on a Windows machine or an Apple Mac. At...
Hace 2 meses
• - Hi, all. I was debating doing a post on this, but the books say to do it–so I will! (Who am I to second guess the wisdom of online marketing eBooks?) Hopef...
Hace 3 meses
• - Immediate PowerBuilder Contract Position Available – Starting Jan/Feb 2017 – \$50 hourly The PowerBuilder Contract Specifics: Location: Boise, Idaho Start: ...
Hace 3 meses
• - En esta ocasión, no vamos a hacer ninguna nueva aplicación, ni ninguna utilidad que no hayamos visto antes en el blog. Lo que voy a presentaros es simpleme...
Hace 4 meses
• - This is an animation of an asynchronous electric motor in Microsoft Excel. You can download the model by clicking on the icon below and try to run it. Wh...
Hace 4 meses
• - Buscador de libros en ExcelPara comenzar bien el año 2017 nada como tener a mano un buen *Buscador de libros en Excel*, en formato pdf, ppt, doc o xls. En ...
Hace 4 meses
• - Interesting diagram and article on knowledge management.
Hace 5 meses
• - *Macro to import data from SQL using ADO connection string:* Sub Import_data_from_SQL() ' Tools -> References -> Microsoft Active Data object 2.0 Dim rs As...
Hace 5 meses
• - [image: Sit down and relax while ASAP Utilities does the rest!]“Everyone can now install ASAP Utilities” One of the improvements in the new version 7.3 is ...
Hace 5 meses
• - Estamos terminando de desarrollar un complemento para que puedas enviar emails desde Excel (te permitirá enviar emails desde cualquiera de tus ficheros Exc...
Hace 5 meses
• - If you’re a developer working for software company, does that company own what you do in your spare time? Read more "Developers’ side projects"
Hace 5 meses
• - I’ve seen it written that Auto_Open() was superseded by Workbook_Open() and that it is therefore redundant and only still available for backward compatibil...
Hace 5 meses
• - Puede descargar el archivo: - indiceDesref.xlsx Hoja1 Disponemos de una tabla de doble entrada con valores de ventas en cinco ciudades durante seis mes...
Hace 6 meses
• - Ya anteriormente he publicado el hacer uso de técnicas como el web scraping para extraer información de páginas web por medio de programación en VBA/Excel....
Hace 6 meses
• - See how an Integrated Planning System in Excel can plan inventory, materials, capacity and production. View a 10 minute demonstration video and get the com...
Hace 9 meses
• - You need the most up-to-date technology to ensure your work isn’t limited by location or circumstance. But what should you look for in your communication...
Hace 9 meses
• - Buenas tardes a todos nuestros amigos y amigas que visitan nuestra web de *planillas Excel de ingeniería civil*, nuevamente les traigo un aporte de nuestro...
Hace 11 meses
• - Dada un Función f: IR ----> IR, tal que f(x)=5x+16. ¿Cuál es el valor de f(3) + f(1)? A) 31 B) 21 C) 4 D) 52 E) 62 *Respuesta:* *Que sea de IR ----> IR, ...
Hace 11 meses
• - *Inga: You know, there's something I've been meaning to ask you. In the transference, the monster got part of your wonderful brain. But what did you ever...
Hace 11 meses
• - Limpiar caracteres no numéricos en Excel Aprende a emplear un conjunto de técnicas que te permitirán limpiar caracteres no numéricos en Excel, de forma p...
Hace 11 meses
• - Just set up meetings, then cancel them. You'll be doubly happy.
Hace 1 año
• - I seems to have inadvertently deleted my Picasa Web folder. As a result all the graphs in the previous posts are missing. I will over the next month or so ...
Hace 1 año
• - *Obligación de presentar los libros contables en el Registro Mercantil* Para la mayoría de las empresas, (aquellas cuyo ejercicio fiscal termina el 31 de ...
Hace 1 año
• - Frau is a free blogger template adapted from WordPress with 2 columns, responsive design, right sidebar, footer columns, slider, social bookmarking icons, ...
Hace 1 año
• - Hi, Recently I came across a great post about SQL Performance Tuning Tips n Tricks, which outlines a good deal of information across all the common feature...
Hace 1 año
• - Download Full The Gunman in HD QualityNow you can enjoy The Gunman in top quality with duration 115 Min and has been launched in 2015-02-16 with MPAA rati...
Hace 1 año
• - Hey just a note to say that this website will be shutting down on November 1st, 2015. I don't really program in VBA anymore, I'm more into mobile now (mo...
Hace 1 año
• - [image: Road Transport Emissions Evolution In Urban Areas; The Case Of Thessaloniki, Greece] ------------------------------ About -------------------------...
Hace 1 año
• - Hola, estimados y queridos visitantes de *este malagradecido blogero excelmaníaco*. Vuelvo luego de meses y meses de inactividad... espero no abandonar nun...
Hace 1 año
• - Hola! Este es un tema bastante buscado y solicitado por la red, hay diferentes formas de obtener buenos resultados, pero este aporte tiene la diferencia q...
Hace 1 año
• - Para poner borde a imágenes de una entrada utilizamos, dependiendo de la ubicación, los siguientes códigos: Imagen a la izquierda <div class="separator...
Hace 2 años
• -
Hace 2 años
• - A new cloud folder is available for downloads. Here. you will find the following sub-folders : - Add-in files for Excel 2007 to 2013 - 32 bits - Add...
Hace 2 años
• - How to calculate Pi by throwing Hotdogs in Excel. This is an implementation of Buffon's Needle in Excel.
Hace 2 años
• - Hola: Respondiendo a este post: Hola! Alguien sabe como puedo crear una macro en word para guardar un documento en pdf cuyo nombre sea la primera linea...
Hace 2 años
• - ExcelCalcs is a community who share an interest in making calculations with MS Excel. Use our XLC add-in for Excel to display cell formulas as easily reada...
Hace 2 años
• - L'événement sportif de l'année, c'est pour bientôt : le 12 Juin 2014. Téléchargez ce fichier pour faire vos simulations ou bien pour lancer un concours de ...
Hace 3 años
• - Adobe’s Portable Document Format or simply PDF is unavoidable and necessary in today’s age of electronic file sharing, storing and exchanging. When you w...
Hace 3 años
• - Training courses for Outlook 2013 Beginner *Calendar basics* Watch these videos to get familiar with the calendar in Outlook 2013. You can keep things si...
Hace 3 años
• - Todo el mundo sabe lo versátil que es Excel, que se puede hacer casi cualquier cosa con este programa; seguramente en esta flexibilidad radica su éxito, ...
Hace 3 años
• - Los últimos post del blog sobre Excel, están siendo dedicados a cómo construir un cuadro de mando. Una herramienta que te permite condensar la información ...
Hace 3 años
• - Las *Tablas dinámicas* sirven para resumir tablas de datos y obtener subtotales, promedios, porcentajes, máximos, mínimos... Pero, antes de hacer nada debe...
Hace 3 años
• - Several years back, I wrote an article on how to use multiple cells to simulate conditional formats that involved more than 3 conditions. Three versions of...
Hace 4 años
• - In part 1 I looked at how FastExcel SpeedTools MEMLOOKUP and AVLOOKUP2 compared to VLOOKUP and INDEX/MATCH for ease of use and power. This post will benchm...
Hace 4 años
• - Hé oui! Le site du Grand Chaman Excel a maintenant une nouvelle adresse. Il y a eu peu d'activités sur mon blog au cours des dernières semaines. La raison ...
Hace 4 años
• - Aún no hemos asimilado la llegada de Office 2010 y ya está disponible para descargar la versión de prueba de Office 2013… No quisiera parecer inmovilista, ...
Hace 4 años
• - Realizar una lista con los productos que necesitamos y que formarán parte de nuestra cesta de la compra nos ayuda a *encontrar la combinación de bienes pr...
Hace 4 años
• - Para crear un esquema automático en Excel, tenemos que contar previamente con una tabla correctamente planificada, que incluya cálculos resumidos creados a...
Hace 5 años
• - I am sharing Excel Addin for converting Numbers to Words. I keep getting mails / comments where people are not able to install the VBA code shared in my ea...
Hace 5 años
• - Top 10 Tallest Buildings in the world Hi friends, today i am going to list the top 10 tallest buildings in the world, made till now.But as its not easy to ...
Hace 5 años
• - This model is useful to study the relationships between two variables (explanatory and explained), for example: amount depending on the price, sales in te...
Hace 6 años
• - Es el objeto siguiente a Application y Workbook en el orden jerárquico de Excel. El objeto Worksheet recoge todos los métodos, propiedades y eventos real...
Hace 6 años