Factoring and Semiprimes

A semiprime (or near prime, pq number, etc.) is a number that only has two prime factors (not necessarily different primes). It is easy for a computer to quickly compute the value of a semiprime if given two prime numbers. For instance, the prime numbers 23 and 73 were used to send the Arecibo message decades ago into space. In the faint chance that an intelligent being intercepts this message, they will be able to arrange the message on a two-dimensional grid. Being a semiprime, the number 1679 only has two factors -- 23 and 73.

Factoring is a computationally difficult endeavor, however. In fact, the difficulty of factoring very large primes sits at the heart of the most secure encryption methods (including RSA especially). If one could find a fast way to factor large semiprimes, he or she would effectively have a way to quickly decrypt an encrypted message.

Here's an example of a large semiprime (yet still small by RSA 512 bit standards): 31,883,349,249,899,479. I know the two primes that make up that number -- but can you find them quickly? We know that at least one of the primes that make up this number has to be equal to or less than the square root of that number. The square root of 31,883,349,249,899,479 is 178,559,091.76 (rounded). One could write a program to check all primes below this number to find the one that divides into the original number. This would give the two primes that make up this semiprime number.

"That isn't so bad! I could write a program to figure it out in a few minutes and it probably wouldn't take but a few seconds to a minute to find the answer!"

Ok ... then try to crack this semiprime that stands between you and cracking MIT's 1999 challenge (which they believe will take more than 30 years to figure out).

n = 631446608307288889379935712613129233236329881833084137558899
077270195712892488554730844605575320651361834662884894808866
350036848039658817136198766052189726781016228055747539383830
826175971321892666861177695452639157012069093997368008972127
446466642331918780683055206795125307008202024124623398241073
775370512734449416950118097524189066796385875485631980550727
370990439711973361466670154390536015254337398252457931357531
765364633198906465140213398526580034199190398219284471021246
488745938885358207031808428902320971090703239693491996277899
532332018406452247646396635593736700936921275809208629319872
7008292431243681

This is the LCS35 MIT Challenge. That's a 2,048 bit modulus. Hell would freeze over well before all the computers in the world could come close to finding the factors of that number by brute force alone. However, there may yet be an undiscovered efficient algorithm that can factor in polynomial time. If such a method were possible, it might be possible to factor this semiprime within the span of years, months or perhaps even days. (That's saying a lot)

Hillary Rodman Clinton -- Please Concede!

Hillary Clinton it is time for you to concede. The democratic party is hurting and hurting bad. Why? Because of your insistence to see this primary drag out until the very end. I tried to remain unbiased during the primary election, but lately you have shown yourself to be concerned with only one thing -- securing the nomination for yourself at any cost.

Just how expensive are these costs? Well, you have driven a deep wedge into the Democratic party. A large chasm has opened up and has polarized many within the party to form strong dislikes towards both candidates. What is most important this election year? In my opinion, it is assuring that McCain fails to win the general election. We need a strong Democratic nominee and, just as importantly, a strong democratic party derived from a solid base.

You fought for the seating of both Florida and Michigan delegates because you stated that their voices should be heard. I wanted to believe that your intentions were pure, but let's not pretend to be naive. Your true intention was to garner the votes of more delegates and include the voters in those states to secure the claim that you have a larger popular vote than Obama.

This afternoon, Democratic National Committee Chairman Howard Dean and Rules and Bylaws Committee Co-Chairs Alexis Herman and Jim Roosevelt issued a joint statement. This is a section from that statement:

“Today, after careful consideration and debate, the Democratic National Committee’s Rules and Bylaws Committee reached an agreement on the two challenges before the Committee on seating delegations from Florida and Michigan. The Committee voted to seat the full Florida delegation with a half-vote each. The RBC accepted the Michigan Leadership Plan as presented today by the Michigan Democratic Party with the exception that each delegate receives a half vote. In addition, the Committee agreed that delegates from both states should be slated under Rules 5, 6, 7, and 12, outlining the candidate’s right of approval. With this decision, the revised total of delegate votes needed to secure the nomination is 2,118."

Shortly afterwards, your campaign made the following press release:

"We strongly object to the Committee’s decision to undercut its own rules in seating Michigan’s delegates without reflecting the votes of the people of Michigan.

The Committee awarded to Senator Obama not only the delegates won by Uncommitted, but four of the delegates won by Senator Clinton. This decision violates the bedrock principles of our democracy and our Party.
We reserve the right to challenge this decision before the Credentials Committee and appeal for a fair allocation of Michigan’s delegates that actually reflect the votes as they were cast."

What strikes me as blatantly unfair is your objection to Obama receiving the delegates won by uncommitted. Obama removed his name from the ballot in Michigan as did the rest of the democratic runners except yourself. Your name was the only name left on the ballot in Michigan. In essence, you are asking that Hillary receive all the delegates that will eventually be seated for the state of Michigan. This is outrageous and clearly demonstrates that your campaign is no longer an honest campaign. You are now hellbent on securing the nomination for yourself at any cost.

Your campaign website now features a popular vote counter. The popular vote is not how we select our nominees and presidents. This is a republic, Senator Clinton, and not a pure democracy. However, it now appears that you will use this fact as another reason to argue that you should receive the nomination.

You had two choices at one point in your campaign. You could have conceded and allowed time for healing and then stood behind Obama by convincing your followers that they should support his nomination and eventual fight against McCain for presidency. Instead, you have chosen to press onward with your need to become the democratic nominee. In the process, you have alienated many within the democratic party and have convinced those that follow you that Obama will never be a good substitute for the democratic nomination.

Senator Clinton, I am now convinced that you do not have the best intentions of this country in your heart. I am convinced that you care only for power and that you will go to any length to achieve your goals. Although I was always an Obama supporter, I did at one point in time respect your accomplishments and would have rallied for you if Obama lost the nomination. I will never rally behind you now.

Thanks for destroying the democratic party by your insatiable lust for power. It sickens me to know that Obama may very well lose to McCain because of your selfish actions during this primary.

Concede now.

Update: Here are some videos from the meeting. DISGUSTING.