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

• - This blog post was written by Bryan Pierce of Perceptual Edge. It’s only a little over seven weeks until Stephen Few will be teaching the West Coast Visual...
Hace 21 horas
• - Hoy jugaremos con uno de los principales músculos del cuerpo humano Pero no es un juego de anatomía, sino de cine. Maruja, sigue con su saga de juegos de...
Hace 1 día
• - En muchas ocasiones necesitamos traducir al inglés las funciones Excel de nuestra hoja... La entrada Traducir al inglés las funciones Excel de nuestra ho...
Hace 1 día
• - Title Problema Necesitamos eliminar todos los hipervínculos de una hoja o de un libro de Excel. Solución 1. Abrimos el Editor de Microsoft Visual Ba...
Hace 1 día
• - Let's say you got some text values and want to extract the amounts from them. Something like above. *How to go about it?* We could use a variety of techniq...
Hace 1 día
• - Plantilla Excel para rendición de viáticos – incluye DD. JJ. de viáticos al exterior es una plantilla Excel que nos permite realizar la rendición del diner...
Hace 1 día
• - Excel ha ido desarrollándose a lo largo de los años en un proceso de permanente adaptación a las necesidades de los usuarios. Esto ha convertido a Excel en...
Hace 2 días
• - En el grupo de facebook que gestiono, un usuario preguntaba por la manera de *conseguir recuperar el valor previo coincidente*. Lo vemos mejor en la imagen ...
Hace 2 días
• - [image: Generate weekend dates only with a simple formula] *In a a world where everyday is Saturday or Sunday....* Here's a little puzzle for you...how ca...
Hace 3 días
• - Hello blogger, do you monetize your blog ? There is easy method to earn decent money every month, just search on youtube - How to earn with wordai 4
Hace 4 días
• - Más largo el título de la entrada que la entrada en si misma. Tenemos un conjunto de datos que os podéis descargar de este link que ya es conocido. Os desc...
Hace 5 días
• - What Are Drop Buttons Drop Buttons are buttons which are part of another control. For example, in a ComboBox, the Drop Button is a small button with an a...
Hace 1 semana
• - What Are Drop Buttons Drop Buttons are buttons which are part of another control. For example, in a ComboBox, the Drop Button is a small button with an a...
Hace 1 semana
• - Following some recent questions in the comments, here are some answers: How can nodal moments be created? The current versions only allow for forces to be ...
Hace 1 semana
• - Slicers make it easy to select from a list of items, but they take up valuable space on your worksheet. To get the benefits of a Slicer, without the real...
Hace 1 semana
• - Variations of the Alternative Bullet Graph Design: Visualization of Gaps and Exceedances, two Targets and two Gaps, conditionally formatted Actuals and dyn...
Hace 1 semana
• - 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 semana
• - I take data that has been entered in Excel and I store it in SQL Server. A lot. I do that a lot. The proper way to do that is to create a stored procedure ...
Hace 2 semanas
• - Me alegra mucho comunicaros que este humilde blog ya tiene más de un millón de visitas. Si miramos las estadísticas podemos apreciar que el número de visi...
Hace 2 semanas
• - This Excel tutorial explains how to assign sequence number to duplicate records using COUNTIF Function. Excel assign sequence number to duplicate records...
Hace 2 semanas
• - Quienes sigáis esta serie sobre números piramidales adivinaréis que los de tipo hexagonal son suma de los primeros números poligonales hexagonales, 1, 6, ...
Hace 3 semanas
• - 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 4 semanas
• - Ik heb vandaag een nieuw artikel toegevoegd over Cocreatie in Excel 2016
Hace 4 semanas
• - Hungarian Notation is a coding convention that many programmers use to (presumably) make their code more understandable. It involves prefixing variable nam...
Hace 4 semanas
• - [Haz clic en el título para ver la nota completa]
Hace 1 mes
• - 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 mes
• -
Hace 2 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 2 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 3 meses
• - 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 3 meses
• - *1. Plantilla Formulario Renta 110 y Formato 1732* Presentamos Formulario Renta Actualizado 110 Persona Jurídica vinculado al Formato 1732 para Declaración...
Hace 3 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 4 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 4 meses
• - […] La entrada Cómo insertar y mover libremente etiquetas de datos en cualquier gráfico de Calc aparece primero en Funcionarioseficientes.
Hace 4 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 4 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 5 meses
• - Immediate PowerBuilder Contract Position Available – Starting Jan/Feb 2017 – \$50 hourly The PowerBuilder Contract Specifics: Location: Boise, Idaho Start: ...
Hace 6 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 6 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 6 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 6 meses
• - Interesting diagram and article on knowledge management.
Hace 7 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 7 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 7 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 7 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 7 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 7 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 8 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 11 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 11 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 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
• - 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 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 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 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 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 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
• - 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 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 6 años