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

• - The latest concert of the excellent Willoughby Symphony Choir featured a collection of popular and folk songs, rather than their usual classical performanc...
Hace 7 horas
• - Este fin de semana vamos a aprender muchas cosas… Porque Princesa nos va a mostrar los logos o escudos de 100 universidades o escuelas mayore...
Hace 10 horas
• - En algunas bases de datos las fechas se guardan en un formato que no es el habitual, un numero que es dificil descifrar a que fecha normal o real hacen ref...
Hace 1 día
• - What an honour and pleasant surprise to be selected as one of the Top 40! Recently I am quite busy (and moody) at work, I mean the real work at office. Yo...
Hace 1 día
• - Ever wondered how to undo in Power Query. If you try to press CTRL+Z or look for undo icon in Power Query (either in Excel or Power BI), you will not fin...
Hace 2 días
• - Seguro te has preguntando muchas veces cuántas horas trabajas al año y si cumples con lo establecido con el convenio que tengas... Hoy explicaremos como con...
Hace 3 días
• - Obtener el promedio de las horas en Excel sin considerar valores de cero y celdas vacías... La entrada Media o Promedio de las horas en Excel aparece pri...
Hace 4 días
• - If you work with any type of data, then you know that rarely does it come perfectly in the format you need. Power Query (also called Get & Transform in E...
Hace 5 días
• - If you work with any type of data, then you know that rarely does it come perfectly in the format you need. Power Query (also called Get & Transform in E...
Hace 5 días
• - Title Problema Crear un mapa coroplético con leaflet es muy sencillo. En nuestro ejemplo, crearemos un mapa coroplético de España con el número de habitan...
Hace 5 días
• - RefTreeAnalyser 2.0 has just been updated. Improved performance of formula checking and reporting significantly.
Hace 1 semana
• - *Otros números piramidales centrados* *Hexagonales* Con estos números, como veremos, el inicio del estudio seguirá un camino más simple: Partimos de l...
Hace 1 semana
• - If you’re planning a vacation trip, Excel can help. It’s a great place to keep your packing lists, and you can track your vacation spending too (if you rea...
Hace 1 semana
• - Ya podéis ver en Youtube la charla que di el pasado mes de diciembre en el evento divulgativo Desgranando Ciencia 4. Espero que os guste.
Hace 1 semana
• - Every once in a while, you might find Excel behaving in a bizarre or unexpected way. One example is when you accidentally trigger the scroll lock featur...
Hace 2 semanas
• - GENERADOR REGISTRO DE VENTAS DESDE XML – FACTURADOR SUNAT Es una macro desarrollada en Excel que nos permite obtener nuestro Registro de Ventas desde los a...
Hace 2 semanas
• - This Excel VBA tutorial explains how to automate AutoFilter to filter value and then copy data to new worksheet or copy data to new workbook. You may al...
Hace 2 semanas
• - Puede descargar el archivo trianguloFloyd.xlsm El triángulo de Floyd para cuatro filas es el siguiente. Se construye con los números naturales en forma de...
Hace 2 semanas
• - I recently purchased a couple of Surface Laptops, that run Windows 10S. I went to install a couple of my Office 365 Pro Plus licenses on them. Now I’m wond...
Hace 3 semanas
• - I received an email a few days ago from the founder and CEO of a new analytics software company that led to an interesting revelation. In his email, this f...
Hace 4 semanas
• - A la hora de seleccionar las características de un data frame es posible que nos encontremos con la necesidad de seleccionar o eliminar características del...
Hace 4 semanas
• - Last updated: 20/05/2018, 1 min read Introduction Some years ago, I published a VBA code that proved to be very popular in blog users: the code and the acc...
Hace 5 semanas
• - To make room for some exciting updates coming soon to Blogger, we’re simplifying the platform to enhance the blogging experience for all of our users. Ch...
Hace 5 semanas
• - New product: Stack Overflow for Teams lets you direct questions to members of your own team, company, or organization. Read more "Announcing Stack Overflow...
Hace 1 mes
• - --> Está publicado el proyecto de resolución del Formulario 210 para Personas Naturales No Obligados a Llevar contabilidad, el cual deberá ser preparado p...
Hace 2 meses
• - This is a guest post from Joseph Helstrom, CPA. *Adding VLookup as a Control for Your Month-End Workpapers* When closing for the month, many use an Excel ...
Hace 3 meses
• - Respuesta: Fuente: NEM: Eje Temático: CMO:
Hace 4 meses
• - 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 4 meses
• - Excel 2016 Performance Improvements The Excel team has made a number of performance improvements to Excel 2016. These improvements were rolled out as part ...
Hace 4 meses
• - [[ This is a content summary only. Visit my website for full links, other content, and more! ]]
Hace 6 meses
• - Un muy buen Calendario Excel 2018. En una hoja se visualizan los 12 meses juntos. También hay una hoja individual para cada mes.
Hace 6 meses
• - [image: Update Excel][last updated: May 9, 2018] Introduction The past year we have received several support requests that we found out were related to/cau...
Hace 7 meses
• - It began with a tweet: Data tweeps: Help! I need to become a competent data viz thinker, well, immediately. Are there "must-read" sources that y'all can ...
Hace 7 meses
• - 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 8 meses
• - 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 9 meses
• - 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 9 meses
• - 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 10 meses
• - ¡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 10 meses
• - 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 11 meses
• - 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 11 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 11 meses
• - Hungarian Notation is a coding convention that many programmers use to (presumably) make their code more understandable. It involves prefixing variable nam...
Hace 11 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 1 año
• -
Hace 1 año
• - 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 1 año
• - […] La entrada Cómo insertar y mover libremente etiquetas de datos en cualquier gráfico de Calc aparece primero en Funcionarioseficientes.
Hace 1 año
• - 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 1 año
• - Immediate PowerBuilder Contract Position Available – Starting Jan/Feb 2017 – \$50 hourly The PowerBuilder Contract Specifics: Location: Boise, Idaho Start: ...
Hace 1 año
• - 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 1 año
• - 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 1 año
• - Interesting diagram and article on knowledge management.
Hace 1 año
• - *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 1 año
• - 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 1 año
• - 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 2 años
• - *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 2 años
• - Just set up meetings, then cancel them. You'll be doubly happy.
Hace 2 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 2 años
• - Frau is a free blogger template adapted from WordPress with 2 columns, responsive design, right sidebar, footer columns, slider, social bookmarking icons, ...
Hace 2 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 2 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 2 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 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 3 años
• -
Hace 3 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 3 años
• - How to calculate Pi by throwing Hotdogs in Excel. This is an implementation of Buffon's Needle in Excel.
Hace 3 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 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 4 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 4 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 4 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 4 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 5 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 5 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 5 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 6 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 6 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 7 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