Math EE on prime factorization and RSA cryptography - viability of discussing quantum computing/algorithms?

[Razorlance]

Hi,

 

For my mathematics Extended Essay I am considering and conducting research on the following topic:

 

Comparing the efficiency of classical and quantum algorithms in the factorization of semiprimes

 

I came about this after doing some reading on RSA factorization and discovering the importance of primes and semiprimes, and was curious how advances in quantum computing posed such a large threat to cybersecurity. My EE supervisor (whom although I think is very proficient in mathematics doesn't seem to be well acquainted with this topic) approved my topic first time and found it suitable. However, I have encountered several challenges that are forcing me to reconsider the viability of this topic:

1. Evaluation and comparison of algorithms seem to be more suited for a Computer Science EE than a Math EE. I don't take CS as a subject, and thus switching my EE subject to CS is out of the question. Looking at factorization methods such as Dixon's algorithm doesn't seem to have lots of 'operable' math that I can analyse or make an argument on, and since the execution is computer based it is difficult for me to make an original argument of the effectiveness of each algorithm based on a mathematical point of view.
2. Many of the involved topics require a very extensive background knowledge in order to be able to fully grasp the theory. I understand that the Extended Essay is intended to be an exercise in writing a research paper, and that math EEs are one of the most difficult EEs out there, but I am beginning to feel that my topic in particular seems to be overcomplicating what is expected of an EE as the topics involved are far too out-of-reach for even a high school student with an ardent interest in mathematics. Sure, I can do research on congruence of squares, but I feel that it is futile to write an EE about integer factorization if I don't fully understand everything behind its algorithms.

 

Is it still possible to write a good EE on this topic? I would appreciate it if advice is given on how the topic can be rectified to be more suitable. If not, could someone help guide me in making a better research question based on integer factorization? Thank you very much.

 

[kw0573]

1. It is possible (as in people have done it before, and IB does not prohibit it) to still do the EE in a subject you are not studying.
2. You are absolutely right about the extensive background knowledge. In a great EE you want to display both knowledge and investigative/creative thinking, yet the latter relies on the former.

So since you have to basically learn lots of college math on your own, you may try to instead in the EE focus on how you came to personally learn these concepts ("by playing around with this and that parameters, I observed, hmm that ....") and the focus would be to explain "how it works" instead of something more in depth. Which is okay, because the topic itself is already quite in depth.

Personally I have also switched my math IA and EE topics half way Year 2, just an option you can consider if it comes down to that.

[Vioh]

Comparing the efficiency of classical and quantum algorithms in the factorization of semiprimes

 

I don't think it's a good idea to write anything about quantum computation in a maths EE at high-school level. The reason is because I'm afraid that you won't be able to fully grasp all the necessary concepts of quantum mechanics (which is part of physics) in order to write an in-depth extended essay. Having read several books about quantum computation, I find this field to be very difficult to study. It requires quite a lot of advanced mathematics, from abstract algebra, vector spaces, matrices, to probability theory. Not only that, to be able to discuss anything relating to quantum algorithms, you'll need to understand the basics of quantum mechanics, including theorems like no-cloning theorem, or superposition principle, etc. Generally, I don't think it's appropriate to include quantum algorithms, simply because it's too difficult. On the other hand, classical algorithms are totally alright to talk about.

 

Evaluation and comparison of algorithms seem to be more suited for a Computer Science EE than a Math EE. I don't take CS as a subject, and thus switching my EE subject to CS is out of the question. Looking at factorization methods such as Dixon's algorithm doesn't seem to have lots of 'operable' math that I can analyse or make an argument on, and since the execution is computer based it is difficult for me to make an original argument of the effectiveness of each algorithm based on a mathematical point of view.

 

Evaluation of algorithms doesn't necessarily belong to CS. Take the Discrete Maths HL Option for example. A large part of the option is about Dikstra's algorithm, Kruskal's algorithm, Chinese Salesman Problem, all of which can be implemented on a computer as a programming algorithm. Even Dixon's algorithm has a lot to do with mathematics. Take a look at the wikipedia article, there is a lot of mathematics involved, especially modular arithmetic which is absolutely central to discrete mathematics.

To make your EE more like a math EE rather than a CS essay, you just need to be extremely careful not to include any CS concepts into the essay. Your essay should be written in such a way that a person who has a mathematics degree in university can understand. So avoid all complicated CS concepts. Only include a brief 'background' knowledge on how computation works (like the basics ideas about bits, for example).

 

Many of the involved topics require a very extensive background knowledge in order to be able to fully grasp the theory. I understand that the Extended Essay is intended to be an exercise in writing a research paper, and that math EEs are one of the most difficult EEs out there, but I am beginning to feel that my topic in particular seems to be overcomplicating what is expected of an EE as the topics involved are far too out-of-reach for even a high school student with an ardent interest in mathematics. Sure, I can do research on congruence of squares, but I feel that it is futile to write an EE about integer factorization if I don't fully understand everything behind its algorithms.

 

Like I've mentioned, you shouldn't include quantum computation into your EE. So that would remove the most difficult part of your idea. Now, you end up with a research question that contains only classical algorithms, which I think isn't very difficult to investigate. I suggest you to discuss this idea with your supervisor in order to find a more narrow and focused question for your EE, instead of just writing endlessly about everything behind the classical algorithms.

Sorry if I couldn't be of more help.