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

• - Following the last post on using the Python version of Alglib from Excel, via xlwings, this post looks in more detail at alternatives for fitting a non-lin...
Hace 1 día
• - Hoy tenemos juego de un nuevo creador en este foro. Evagg, que como ya dijo cuando se presentó en el foro, hace años creaba juegos que se publicaban en otr...
Hace 1 día
• - Apps Script runs on Google Servers, probably the Rhino JavaScript engine running on Google App Engine. Rhino is written in Java and the implementation use...
Hace 2 días
• - Vamos a repasar unas *propiedades de la aplicación*, de Excel, que nos pueden ser útiles en diferentes ocasiones. Por ejemplo, cuando trabajamos con nuestra...
Hace 3 días
• - En la nota anterior mostramos como calcular las horas trabajadas por un empleado a partir de un informe en una hoja de Excel usando Power Query. En un caso...
Hace 3 días
• - As you know, pivot tables are a quick and easy way to summarize a huge table of data in Excel. With just a few clicks, you can create totals for thousand...
Hace 3 días
• - Al trabajar con valores de fecha, nos puede interesar insertar una fecha que no sea sábado ni domingo en Excel... La entrada Insertar una fecha que no se...
Hace 3 días
• - This Access tutorial explains how to add sorting in Access Table field. You may also want to read: Sort Data in Access Report Add Auto number in Access Q...
Hace 4 días
• - I have added a new add-in to my site called Table Tools. This add-in makes your daily life with Excel tables a little simpler!
Hace 4 días
• - Hello friends, It's here. *Power BI Play Date* - our online training program is now ready for your consideration. Please take a few minutes to read this to...
Hace 4 días
• - Casi que me da vergüenza escribir esta nueva entrada... ya que lo hago luego de dos años sin aparecer por estos pagos. ¿Excusas? Miles: trabajo, casa, estu...
Hace 4 días
• - *Condicionamientos sobre las particiones de un conjunto* En la entrada anterior de esta serie ( http://hojaynumeros.blogspot.com.es/2017/06/cartesius-5-part...
Hace 6 días
• - Se ha encontrado con archivos o listados muy largos que tienen celdas en blanco y para realizar sumatorias, conteos y otros necesita tener todas las celdas...
Hace 1 semana
• - Macro para realizar descargo de detracciones a SUNAT – Causal 1 hace unos días un cliente me escribió a mi correo solicitándome ayuda para presentar un arc...
Hace 1 semana
• - [image: Tip: Excel formula errors and fixes] In this video, we'll review the error codes that Excel displays when there's something wrong with a formula. ...
Hace 1 semana
• - En Youtube se pueden encontrar infinidad de vídeos geniales sobre ciencia. Desafortunadamente, también hay mucha porquería. Para resaltar lo bueno frente a...
Hace 2 semanas
• - A user of my Peltier Tech Charts for Excel 3.0 asked recently whether this program could perform interactive formatting of all series 2 in a set of chart...
Hace 2 semanas
• - A user of my Peltier Tech Charts for Excel 3.0 asked recently whether this program could perform interactive formatting of all series 2 in a set of chart...
Hace 2 semanas
• - I made a new version of my Application Settings addin as per Sébastien’s comments in my last post. As you can see, there are new settings for the following...
Hace 3 semanas
• - Using VBA to get the last row in Excel can be a surprisingly complex task. This post will explore some of the different strategies you can use. The first t...
Hace 3 semanas
• - Title Problema Cuando filtramos un data frame que contiene un factor, y creamos por ejemplo una tabla de contingencia, R nos muestra también aquellos nivel...
Hace 3 semanas
• - Let me start with an apology for leaving it so long without a post. It's been a busy time work-wise and, in addition, I've taken up running to finally lose...
Hace 5 semanas
• - Como sabéis Correos (empresa de capital 100% público) ha decidido no colaborar con CartoCiudad (leer los comentarios de este enlace) y poner precio a los m...
Hace 5 semanas
• - Despite the rhetoric of recent years, data is neither beautiful nor ugly. Data is data; it merely describes what is and has no aesthetic dimension. The wor...
Hace 5 semanas
• - Empiezan los vencimientos de Renta Persona Natural, tenga en cuenta las fechas de vencimiento. La DIAN ha dispuesto una serie de Ayudas para su declaraci...
Hace 1 mes
• - A small VBA code snippet to display the most important metrics of an Excel workbook like the count of sheets, cells, formulas, constants, named ranges, cha...
Hace 1 mes
• - ¡Hasta pronto!: EXCELLENTIAS.COM cierra sus puertas No ha sido una decisión sencilla. A partir del mes de Agosto del 2017, EXCELLENTIAS.COM se despide. D...
Hace 1 mes
• - Hace tiempo que he decidido abandonar este blog y pasarme a http://mexcelmx.blogspot.mx/ Sobre todo, que por motivos profesionales estoy trabajando de la m...
Hace 2 meses
• - Hasta la vista Estimado suscriptor: Voy a cerrar el proyecto Ideas Excel en breve, por lo que ya no recibirás más actualizaciones de este sitio, que dejará...
Hace 2 meses
• - Hungarian Notation is a coding convention that many programmers use to (presumably) make their code more understandable. It involves prefixing variable nam...
Hace 2 meses
• - It’s finally time that you got your clothing store in good running order with the free Clothing Store Inventory Keeper. This Excel template was designed ...
Hace 3 meses
• -
Hace 4 meses
• - 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 4 meses
• - 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 5 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 6 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 6 meses
• - […] La entrada Cómo insertar y mover libremente etiquetas de datos en cualquier gráfico de Calc aparece primero en Funcionarioseficientes.
Hace 6 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 7 meses
• - Immediate PowerBuilder Contract Position Available – Starting Jan/Feb 2017 – \$50 hourly The PowerBuilder Contract Specifics: Location: Boise, Idaho Start: ...
Hace 7 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 8 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 8 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 8 meses
• - Interesting diagram and article on knowledge management.
Hace 9 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 9 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 9 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 9 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 9 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 9 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 10 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 1 año
• - 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 1 año
• - 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 1 año
• - 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 1 año
• - *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 1 año
• - 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 2 años
• - 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 2 años
• - 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 3 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 4 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 4 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
• - 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 5 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 6 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 7 años