`Are you a math genius?' `Can you fix my Iphone?' `What do you think about Facebook and Privacy?'

When I meet non-math people and tell them I am a computer science professor I get a range of responses. Here are some and my responses.


1) Are you a math genius?

Here is the answer I give:

I know some things in math, frankly obscure things, that most people in math don't know. On the other hand, I probably can't help your teenage daughter with her trigonometry homework. Academics, like most people, forget what they don't use, and there are some things in math I rarely use, so I've forgotten them.

I wonder how a Fields' Medal winner would answer the question.

Although the above is the answer I give I really think its an ill defined and pointless question. Its very hard to measure genius or even define what it means (there are exceptions). After a certain age, what you've done is more important than how smart you allegedly are.

2) Can you fix my iPhone?

That's an easy one: No. I work on the math end of computer science. I don't elaborate.

3) What do you think of Facebook and privacy?

This is an odd one. I DO have opinions on this but they are NOT better informed just because I'm a comp sci professor. Since I don't have a Facebook account my opinions might be worse informed. So how do I respond? I show them

this Onion News Network Video about how the CIA created Facebook

Some think it's real. They may be right.

Obstacles to improving Classical Factoring Algorithms

In Samuel Wagstaff's excellent book The Joy of Factoring (see here for a review) there is a discussion towards the end about why factoring algorithms have not made much progress recently. I
paraphrase it:


--------------------------------------------------------

The time complexities of the fastest known algorithms can be expressed as a formula of the following form (where N is the number to be factored):

(*) exp(c(ln N)^t (ln(ln N))^{1-t})

for some constants c and for 0 < t < 1. For the Quadratic Sieve (QS) and Elliptic Curve Method (ECM) t=1/2. For the Number Field Sieve (NFS) t=1/3. The reason for this shape for the time complexity is the requirement of finding one or more smooth numbers (numbers that have only small primes as factors).

----------------------------------------------------------

This got me thinking: Okay, there may not be a drastic improvement anytime soon but what about just improving t? Is there a mathematical reason
why an algorithm with (say) t=1/4 has not been discovered? In an earlier era I would have had to write a letter to Dr. Wagstaff to ask him. Buy an envelope, buy a stamp, find his address, the whole nine yards (my younger readers should ask their grandparents what envelopes and stamps were). In the current era I emailed him. And got a response.


Samuel Wagstaff:

The fastest known factoring algorithms find smooth numbers subject to parameter choice(s). In all these algorithms, one parameter choice is the smoothness bound B: a number is smooth if all its prime factors are < B. The NFS has the degree of a polynomial as an additional parameter.

One analyzes the complexity of these algorithms by estimating the total work required (to find enough smooth numbers) for an arbitrary parameter choice using Dickman's function to predict the density of smooth numbers. Then one uses calculus to find the parameter choice(s) that minimize the total work function. Calculus also yields the optimal values for the parameter(s).

If you have k parameters to choose, you will get the time complexity (*) with t = 1/(1+k). If you have no parameters (k = 0),you get (*) with t = 1, basically exponential time N^c. With one parameter to optimize, as in CFRAC (continued fractions algorithm) and QS, you get t = 1/2. NFS has two parameters, so t = 1/3. ECM also has t = 1/2 because it uses only one parameter, the smoothness bound B. If you want to get t = 1/4, you have to find a third parameter to optimize. No one has found one yet. That is the answer to your question.

Note that some choices made in some factoring algorithms don't count as parameters. For example, the number of polynomials used in the multiple-polynomial quadratic sieve, and the upper bound on large primes kept, don't affect t. They affect the running time only in making c smaller. So you have to find a third parameter that matters in order to get (*) with t = 1/4. Or find three completely different new parameters.