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.

Turing to be on the Bank of England 50 pound note, giving me an excuse to talk about Turing

BILL: Darling, guess who is soon going to be on the Bank of England 50 pound note?

DARLING: Alan Turing.

BILL: How did you deduce that? (She is right, see here.)

DARLING: Since you asked it, it couldn't be a member of the Royal Family (you don't care about that) or some British Politician (you don't care about that either). It had to be a mathematician or computer scientist.

BILL: It could have been Hardy. I wonder if Ramanujan could qualify---do they need to be British? At this website it says



Of course, banknotes need to be universally accepted. We therefore look for UK characters who have made an important contribution to our society and culture through their innovation, leadership or values. We do not include fictional characters, or people who are still living (except the monarch on the front of the note). Finally, we need to have a suitable portrait of the person which will be easy to recognise.

(They spell recognise with an s instead of a z, so spellcheck flagged it, but I won't change it.)

Note that people on the banknotes have to be UK characters. I honestly don't know if that means they must be citizens.

OKAY, so here are a few thoughts on Turing.

1) When I visited Bletchley Park there was a booklet that bragged about the fact that Bletchley Park was much better at cracking codes than Germany because they allowed people to work there based only on ability (unlike Germany) - women worked there, Turing who was Gay worked there. I think this is simplistic. Did any Jews work there (anti-semitism was widespread in England, and the world, at the time)? I doubt any blacks worked there since if they did that would be well known by now (if I am wrong let me know). Women DID work there but was their work respected and used? (I honestly don't know). Did Germany also use women at their codebreaking centers? Was Turing known to be gay (if not then Bletchley gets no points for tolerating him). Was JUST having Turing the reason they could crack codes. Plus I am sure there were other factors aside from merit-only.

2) Turing was given a Pardon for his ``crimes'' in August 2014. When I see things like this I wonder who was against it and why and if they were an obstacle.

a) Human Rights Advocate Peter Tatchell noted that its wrong to just single out Turing. Other people prosecuted under that law who did not help beat the German's in WW II should also be pardoned. The government later DID such a pardon in 2017.

b) Judge Minister Lord McNally objected to the pardon:

A posthumous pardon was not considered appropriate as Alan Turing was properly convicted of what at the time was a criminal offence. He would have known that his offence was against the law and that he would be prosecuted. It is tragic that Alan Turing was convicted of an offence that now seems both cruel and absurd—particularly poignant given his outstanding contribution to the war effort. However, the law at the time required a prosecution and, as such, long-standing policy has been to accept that such convictions took place and, rather than trying to alter the historical context and to put right what cannot be put right, ensure instead that we never again return to those times.


While I disagree with him, I do note that, based on what he wrote and his general record, I think he is not saying this from being anti-gay. There is a hard general question here: how does a society right past wrongs? I think pardoning and apologizing is certainly fine, but frankly it seems to weak. What else could a society due? Financial renumeration to living relatives? I don't think giving Inagh Payne (Turing's niece, who I think is still alive) would really help here.

c) At the bill's second reading in the House of Commons on 29 November 2013, Conservative MP Christopher Chope objected to the bill, delaying its passage


I couldn't find Chope's reasons. On the one hand, they may be similar to McNally's. On the other hand he is against same sex marriage so its possible (though I do not know this) that he anti-gay and that is why he is against the pardon. If someone can find what his explanation for blocking the Turing bill is, or other evidence that he is anti-gay, please leave it in the comments.

3) Did the delay matter? I was surprised to find out---Yes. Here is the full passage from Wikipedia:


At the bill's second reading in the House of Commons on 29 November 2013, Conservative MP Christopher Chope objected to the bill, delaying its passage. The bill was due to return to the House of Commons on 28 February 2014,[175] but before the bill could be debated in the House of Commons,[176] the government elected to proceed under the royal prerogative of mercy. On 24 December 2013, Queen Elizabeth II signed a pardon for Turing's conviction for "gross indecency", with immediate effect.[17] Announcing the pardon, Lord Chancellor Chris Grayling said Turing deserved to be "remembered and recognised for his fantastic contribution to the war effort" and not for his later criminal conviction.[16][18] The Queen officially pronounced Turing pardoned in August 2014.[177] The Queen's action is only the fourth royal pardon granted since the conclusion of the Second World War.[178] Pardons are normally granted only when the person is technically innocent, and a request has been made by the family or other interested party; neither condition was met in regard to Turing's conviction.[179]

This amazed me! I thought the Queen had NO power (too bad--- I wish she could just say NO BREXIT). Or that she formally has power but if she ever used it, it might be blocked somehow and taken away. So I am surprised she has a power she can use at all.

4) I wonder if the Pardon had to happen before they put him on the Banknote. I have been told that this is a very American Question--- England has no Constitution and operates more on Custom and Tradition than on written rules.

5) I had always assumed that Turing committed suicide. Without going into detail, the Wikipedia site on Turing does give intelligent counterarguments to this. See here

The Advisor/Advisee Relationship

I've always felt a strong advisor/advisee relationship is the single most important factor in a successful PhD career. At its best, the advisor works closely with the student to successful research agenda and help mentor them through their graduate career and beyond. The advisor/advisee relationship can feel like a parent/child relationship that lasts an entire career. Nothing gives me more pleasure as an academic than to see the success of my current and former students.

Take your time when picking an advisor. Don't choose an advisor based solely on research area or because they are "famous". Pick the advisor that will best guide you to a successful academic career.

At its worst, a bad advisor/advisee relationship will destroy your graduate career, making you feel miserable, perhaps dropping out of graduate school or worse, particularly if a student doesn't feel like they are being treated fairly.

Two incidents prompted this post. On TCS-Stack Exchange, a student has authorship issues with their advisor. Unfortunately these kinds of incidents happen more often than one suspects. If you can't work it out with the advisor, go talk to someone about it, another faculty, the graduate or department chair, a grad student ombudsperson if your institution has one. We care about our students, and will work hard to resolve problems.

In a much more tragic event, a student felt it easier to take his own life than feeling that he had to cover up potential academic misconduct. Again, if you ever find yourself in such a situation please reach out. Giving up is never the answer.

Answer to both Infinite Hats Problems from the last post

(This is a joint post with David Marcus. You'll see why later.)

In a prior I posed two infinite hat problems. Today I post the solutions. Actually this is a copy of my last post with the solutions added, so it is self contained.

A Hat Problem that you have probably seen:

1) There are an infinite number of people, numbered 1,2,3,... There are 2 colors of hats. They can all see everyone's hat but their own.

2) The adversary is going to put hats on all the people. They will guess their own hat color at the same time.

3) The people can discuss strategy ahead of time, but must use a deterministic strategy and the adversary knows the strategy.

4) The people want to minimize how many they get wrong.

5) The adversary puts on hats to maximize how many they get wrong.

I ask two questions (the answers are in a document I point to) and one meta-question:

Q1: Is there a solution where they get all but a finite number of the guesses right? (If you have read my prior post on hat puzzles, here then you can do this one.)

Q2: Is there a solution where they get all but at most (say) 18 wrong.


Answers to Q1 and Q2 are here.

How did I get into this problem? I was looking at hat problems a while back. Then I began discussing Q1 and Q2 by email (Does the term discussing have as a default that it is by email?) with David Marcus who had just read the chapter of Problems with a Point on hat puzzles. After a few emails back and fourth, he began looking on the web for answers. He found one. There is a website of hat puzzles! It was MY website papers on Hat Puzzles! It is here. And on it was a relevant paper here. We did not find any other source of the problem or its solution.

Q3: How well known is problem Q2 and the solution? I've seen Q1 around but the only source on Q2 that I know of is that paper, and now this blog post. So, please leave a comment telling me if you have seen Q2 and/or the solution someplace else, and if so where.

The responses to my last post indicated that YES the problem was out there, but the proof that you could not get all-but-18 was not well known.

I THINK that all of the proofs that you can't do all-but-18 in the comment of the last post were essentially the same as the solution I pointed to in this blog. I would be interested if there is an alternative proof.

Guest post by Samir Khuller on attending The TCS Women 2019 meeting

(I will post the solution to the problem in the last blog later in the week---probably Thursday. Meanwhile, enjoy these thoughts from Samir Khuller on the TCS Women 2019 meeting.)

Guest Post by Samir Khuller:

Am I even allowed here?” was the first thought that crossed my mind when I entered the room. It was packed with women (over 95%), however a few minutes later, several men had trickled in. I was at the TCS Women spotlight workshop on the day before STOC. Kudos to Barna Saha, Sofya Raskhodnikova, and Virginia Vassilevska Williams for putting this grand (and long needed) event together, which serves as a role model and showcases some of the recent work by rising stars. In addition to the Sun afternoon workshop, the event was followed by both an all women panel and a poster session (which I sadly did not attend).


The rising stars talks were given by Naama Ben-David (CMU), Andrea Lincoln (MIT), Debarati Das (Charles University) and Oxana Poburinnaya (Boston U). After a short break the inspirational talk was by Ronitt Rubinfeld from MIT.  Ronitt’s talk was on the topic of Program Checking, but she made it inspirational by putting us in her shoes as a young graduate student, three decades back, trying to make a dent in research by working on something that her advisor Manuel Blum, and his senior graduate student Sampath Kannan had been working on, and I must say she made a pretty big dent in the process! She also related those ideas to other pieces of work done since in a really elegant manner and how these pieces of work lead to work on property testing.


I am delighted to say that NSF supported the workshop along with companies such as Amazon, Akamai, Google and Microsoft. SIGACT plans to be a major sponsor next year.


The Full program for the workshop is at the following URLhere.

Two infinite hat problem and a question about what is ``well known''

This is a joint post with David Marcus. You will see how he is involved in my next post.

Two infinite hat problems based on one scenario. I am also curious if they are well known.

1) There are an infinite number of people, numbered 1,2,3,... There are 2 colors of hats. They can all see everyone's hat but their own.

2) The adversary is going to put hats on all the people. They will guess their own hat color at the same time.

3) The people can discuss strategy ahead of time, but must use a deterministic strategy and the adversary knows the strategy.

4) The people want to minimize how many they get wrong.

5) The adversary puts on hats to maximize how many they get wrong.

I ask two questions and one meta-question:

Q1: Is there a solution where they get all but a finite number of the guesses right? (I have blogged about a variant of this one a while back.)

Q2: Is there a solution where they get all but at most (say) 18 wrong. (My students would say the answer has to be YES or he wouldn't ask it. They don't realize that I work on upper AND lower bounds!)

Q3: How well known is problem Q1 and the solution? Q2 and the solution? I've seen Q1 and its solution around (not sure where), but the only source on Q2 that I know of is CAN'T TELL YOU IN THIS POST, WILL IN THE NEXT POST. So, please leave a comment telling me if you have seen Q1 or Q2 and solutions. And if so then where.

Feel free to leave any comments you want; however, I warn readers who want to solve it themselves to not look at the comments, or at my next post.

Degree and Sensitivity

Hao Huang's proof of the sensitivity conjecture that I posted on last week relied on a 1992 result of Gotsman and Linial. Let's talk about that result.

Consider the set S={-1,1}ⁿ. The hypercube of dimension n is the graph with vertex set S and an edge between x = (x₁,…,x_n) and y = (y₁,…,y_n) in S if there is exactly one i such that x_i ≠ y_i. Every vertex has degree n.

We say a vertex x is odd if x has an odd number of -1 coordinates, even otherwise. Every edge joins an odd and even vertex.

Let f be a function mapping S to {-1,1}. The sensitivity of f on x is the number of i such that f(x₁,…,x_i,…,x_n) ≠ f(x₁,…,-x_i,…,x_n). The sensitivity of f is the maximum over all x in S of the sensitivity of f on x.

Let g be the same function as f except that we flip the value on all odd vertices. Notice now that the sensitivity of f on x is the number of i such that g(x₁,…,x_i,…,x_n) = g(x₁,…,-x_i,…,x_n).

Let G be the induced subgraph of vertices of x such that g(x)=-1 and H be induced subgraph on the set of x such that g(x)=1. The sensitivity of f is the maximum number of neighbors of any vertex in G or H.

Consider f as a multilinear polynomial over the reals. The sensitivity conjecture states there is some α>0 such that if f has degree n then f has sensitivity at least n^α.

Note g(x₁,…,x_n)=f(x₁,…,x_n)x₁⋯x_n. If f has a degree n term, the variables in that term cancel out on S (since x_i²=1) and the constant of the degree n term of f becomes the constant term of g. The constant term is just the expected value, so f has full degree iff g is unbalanced.

GL Assumption: Suppose you have a partition of the hypercube into sets A and B with |A| ≠ |B|, and let G and H be the induced subgraphs of A and B. Then there is some constant α>0 such that there is a node of A or B with at least n^α neighbors.

The above argument, due to Gotsman and Linial, shows that the GL assumption is equivalent to the sensitivity conjecture.

Huang proved that given any subset A of the vertices of a hypercube with |A|>2ⁿ/2 the induced subgraph has a node of degree at least n^1/2. Since either A or B in the GL assumption has size greater than 2ⁿ/2, Huang's result gives the sensitivity conjecture.

Fortran is underated!

(Joint Post with David Marcus who was a classmate of mine at SUNY Stony Brook [now called Stony Brook University]. I was class of 1980, he was class of 1979. We were both math majors.)

David has been reading Problems with a POINT (I'm glad someone is reading it) and emailed me a comment on the following passage which was essentially this post. I paraphrase what I wrote:

PASSAGE IN BOOK:
I dusted off my book shelves and found a book on Fortran. On the back it said:

FORTRAN is one of the oldest high-level languages and remains the premier language for writing code for science and engineering applications. (NOTE- The back of the book uses Fortran but the spell checker I am using insists on FORTRAN. As a fan of capital letters, I don't mind going along.)

When was the book written?

The answer was surprising in that it was 2012 (the Chapter title was Trick Question or Stupid Question. This was a Trick Question.) I would have thought that FORTRAN was no longer the premier language by then. I also need to dust my bookshelves more often.
END OF PASSAGE IN BOOK

David Marcus emailed me the following:

DAVID'S EMAIL
Page 201. Fortran. One clue is that it said "Fortran" rather than"FORTRAN". Fortran 90 changed the name from all upper case. Whether it is the "premier language" depends on what you mean by "premier". It is probably the best language for scientific computing. I used it pretty much exclusively (by choice) in my previous job that I left in 2006. The handling of arrays is better than any other language I've used. Maybe there are some better languages that I'm not familiar with, but the huge number of high-quality scientific libraries available for Fortran makes it hard to beat. On the other hand, I never wrote a GUI app with it (Delphi is best for that).
END OF DAVID'S EMAIL

In later emails we agreed that Fortran is not used that much (there are lists of most-used languages and neither Fortran nor FORTRAN is ever in the top 10). But what intrigued me was the following contrast:

1) David says that its the BEST language for Scientific Computing. I will assume he is right.

2) I doubt much NEW code is being written in it. I will assume I am right.

So---what's up with that? Some options

OPTION 1) People SHOULD use Fortran but DON'T. If so, why is that? Fortran is not taught in schools. People are used to what they already know. Perhaps people who do pick up new things easily and want to use new things would rather use NEW things rather than NEW-TO-THEM-BUT-NOT-TO-THEIR-GRANDMOTHER things. Could be a coolness factor. Do the advantages of Fortran outweight the disadvantages? Is what they are using good enough?

OPTION 2) The amount of Scientific computing software being written is small since we already have these great Fortran packages. So it may be a victim of its own success.

CAVEAT: When I emailed David a first draft of the post he pointed out the following which has to do with the lists of most-used programming languages:

DAVIDS EMAIL:
The problem with the lists you were looking at is that most people in the world are not scientists, so most software being written is not for scientists. Scientists and technical people are writing lots of new code. If you look at a list of scientific languages, you will see Fortran, e.g., here and here.


There are several Fortran compilers available. One of the best was bought by Intel some time back and they still sell it. I doubt they would do that if no one was using it. Actually, I think Intel had a compiler, but bought the Compaq compiler (which used to be the Digital Equipment compiler) and merged the Compaq team with their team. Something like that. I was using the Compaq compiler around that time.
END OF DAVID's EMAIL

One quote from the second pointer I find intriguing. (Second use of the word intriguing. It was my word-of-the-day on my word-calendar).

... facilities for inter-operation with C were added to Fortran 2003 and enhanced by ISO/ICE technical specification 29113, which will be incorporated into Fortran 2018.

I (Bill) don't know what some of that means; however, it does mean that Fortran is still active.


One fear: with its not being taught that much, will knowledge of it die out. We be like Star Trek aliens:

The old ones built these machines, but then died and we can't fix them!