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

• - Problem In the following plot created using geom_tile we have rectangular cells. How can we draw squared cells instead? set.seed(1) df <- data.frame(val ...
Hace 6 horas
• - Doodle, logotipo en la página principal de Google que pretende celebrar fiestas, eventos, logros o personas. Princesa, nos trae un tercer juego de los que ...
Hace 8 horas
• - Aprenderemos en el post de hoy a *elegir una de nuestras cuentas de Outlook desde la que enviar nuestros emails*... [...] en mi outlook tengo configurada m...
Hace 12 horas
• - Malinda Kathleen Reese mostly sings popular songs, after passing the lyrics through Google Translate multiple times. But this is something else:
Hace 15 horas
• - Normalmente pensamos en aleatorio, cuando requerimos numeros, pero en ciertas ocasiones, necesitaremos lo mismo pero para horas. La funcion aleatorio, y a...
Hace 1 día
• - Cuando necesitamos editar texto sólo en el área deseado de la hoja Excel podemos recurrir a macros... La entrada Editar texto sólo en el área deseado de ...
Hace 1 día
• - Last Friday was a public holiday in Hong Kong. Yes, a long weekend! Guess what I dd over the long weekend? I’ve created a playlist – “Excel Magic in One...
Hace 4 días
• - I recently went to Sydney to conduct some training programs on Advanced Excel and Power BI. While I was there, I met my good friend Danielle, who runs Pl...
Hace 4 días
• - I usually do an annual post on what's been going on in the world of Apps Script, like this one but since we're coming up to the platform's 10th anniversary...
Hace 5 días
• - Last week, someone asked if I could stop zipping the sample Excel files that you can download from my website. Well, I thought about it carefully, and deci...
Hace 5 días
• - En español: 3 Aplicaciones que uso para proteger mis ojos. Being in front of a computer or a cellphone for long periods of time (beside aging, of course)...
Hace 6 días
• - En la iteración de la entrada anterior de esta serie (es importante su repaso), los números que desembocan en la unidad reciben el nombre de “números fel...
Hace 1 semana
• - Extraer imágenes de una Hoja Excel este procedimiento es similar al anteriormente explicado (extraer imágenes de un Ribbon) y puede resultar muy útil cuand...
Hace 1 semana
• - Floating Bars and Gantt Charts Gantt charts are a special kind of floating bar chart used in scheduling and program management. A list of tasks or activi...
Hace 2 semanas
• - Floating Bars and Gantt Charts Gantt charts are a special kind of floating bar chart used in scheduling and program management. A list of tasks or activi...
Hace 2 semanas
• - A medida que los tiempos cambian también lo hacen nuestra manera de argumentar, incluso aunque las ideas de fondo se mantengan. Si hace un par de décadas...
Hace 3 semanas
• - Office 365 Excel Dynamic Arrays are great, but: What happens when you create a workbook with Dynamic Array Excel (Excel DA) and send it to someone who doe...
Hace 4 semanas
• - After a few months of waiting, my new book The Data Loom: Weaving Understanding by Thinking Critically and Scientifically with Data is now available. By cl...
Hace 4 semanas
• - Formula errors are a fact of life in Excel. The more formulas you write, the more errors you'll run into :) Although frustrating, formula errors are use...
Hace 4 semanas
• - This Excel tutorial explains how to use distinct count in Pivot Table to count number of unique value in a column grouped by other fields. Excel Pivot Ta...
Hace 5 semanas
• - Hi Zhen! In this case I've chosen 3 different random frequencies (in that particular input function - however there are three input functions you can selec...
Hace 5 semanas
• - Puede descargar el archivo VanTir.xlsm El Valor Actual Neto (VAN) habitualmente se calcula utilizando un tipo de interés fijo. En esta ocasión vamos a calc...
Hace 1 mes
• - New multi-tool data visualization learning site.You'll find low-cost, short, focused and practical courses on multiple topics and step-by-step instructio...
Hace 1 mes
• - A minigun animation in MS Office to possibly be used in future games. Graphics created in PowerPoint and Excel animation using 100% VBA. Join our group t...
Hace 2 meses
• - *Tired of Nesting IF after IF?Get off the Nest and use IFS()* IFS() is a Logical Function that can be found in Excel 2019 and Office 365. This function a...
Hace 2 meses
• - Sorting a list is a very common use of Excel but there are a few things to consider when you do, and a few extra features that you may not be aware of. The...
Hace 2 meses
• - I've added a new feature to the Compare2Tables tool. You can now select which difference tables you want the tool to produce.
Hace 2 meses
• - We’re looking for a new CEO for Stack Overflow. I’m stepping out of the day-to-day and up to the role of Chairman of the Board. Read more "The next CEO of ...
Hace 2 meses
• - Saludos a todos que visitan nuestra web de planillas Excel de ingeniería civil, presentamos ahora ésta Planilla Excel que consta de varias hojas que les ay...
Hace 2 meses
• - *Inga: Disa what?* *Igor: -ppeared.* by The FrankensTeam ------------------------------ Really it was 3 years ago we posted our last article? *Freddy: Th...
Hace 2 meses
• - Un muy buen Calendario Excel 2019. En una hoja se visualizan los 12 meses juntos. También hay una hoja individual para cada mes.
Hace 2 meses
• - Siempre he querido hacer cosas con Rstats y el Quijote y ayer se me ocurrió medir la longitud de las frases del Quijote y crear un histograma que describa ...
Hace 3 meses
• - Following the announcement of Google+ API deprecation scheduled for March 2019, a number of changes will be made to Blogger’s Google+ integration on 4 Febr...
Hace 4 meses
• - [image: Quickly Clean Up Data and Formatting in Excel]Save 5 minutes a day by using ASAP Utilities to quickly clean up your data in Excel. "Easily optimize...
Hace 5 meses
• - Last updated: 05/01/2019, 1 min read (without the code) Introduction We have already seen how to send emails directly from Google Sheets. In this post, we ...
Hace 5 meses
• - Hace mucho que no actualizo ninguna información en el blog, ni para dar consejos de Excel, ni para comentar los cambios que voy haciendo en el sitio web,...
Hace 5 meses
• - Reciba Notificaciones de Noticias
Hace 6 meses
• - In the grand tradition of Keyboard Shortcut Metrics and More Keyboard Metrics, here’s this: Procedure 2016 2017 2018 Grand Total MakeComma 20.54% 18.67% 19...
Hace 7 meses
• - Respuesta: Fuente: NEM: Eje Temático: CMO:
Hace 1 año
• - Nueva Agenda Calendario de Fases LunaresNew Moon Phases Calendar PlannerHe creado y acabo de publicar una nueva agenda calendario de fases lunares, con la ...
Hace 1 año
• - Hace varios días que venía dándole vueltas a la idea de mostrar cómo crear una tabla de amortización de préstamos, como el modelo que publiqué en el pasado...
Hace 1 año
• - 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 1 año
• - 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 año
• - ¡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 año
• - 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 1 año
• - 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 1 año
• - 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 1 año
• - Hungarian Notation is a coding convention that many programmers use to (presumably) make their code more understandable. It involves prefixing variable nam...
Hace 1 año
• - 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 2 años
• -
Hace 2 años
• - 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 2 años
• - […] La entrada Cómo insertar y mover libremente etiquetas de datos en cualquier gráfico de Calc aparece primero en Funcionarioseficientes.
Hace 2 años
• - 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 2 años
• - Immediate PowerBuilder Contract Position Available – Starting Jan/Feb 2017 – \$50 hourly The PowerBuilder Contract Specifics: Location: Boise, Idaho Start: ...
Hace 2 años
• - 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 2 años
• - Interesting diagram and article on knowledge management.
Hace 2 años
• - *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 2 años
• - 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 2 años
• - 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 2 años
• - 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 2 años
• - In this article we will show you how to create an Invoice template using MS Excel by using simple functions. An invoice is a little piece of paper that pro...
Hace 3 años
• - Just set up meetings, then cancel them. You'll be doubly happy.
Hace 3 años
• - 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 3 años
• - 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 3 años
• - 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 3 años
• - 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 3 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 3 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 4 años
• -
Hace 4 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 4 años
• - How to calculate Pi by throwing Hotdogs in Excel. This is an implementation of Buffon's Needle in Excel.
Hace 4 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 4 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 5 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 5 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 5 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 5 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 5 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 6 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 6 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 6 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 6 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 7 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 7 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 7 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 8 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 8 años