pranavappu007 wrote:
I assume the 'individual' is me.
Yeah. I saw this proof years ago in uni and never found it again, so I went for a search for it. Amazing what you can find on the Internet. But your interest in RSA only prompted me to look it up again.
pranavappu007 wrote:
It seems that you have gone through the hassle to prove a very difficult algorithm in response to my post,
Nah. If it were a response I would have responded. This was entirely off-topic in that other thread. Also, I didn't actually create this proof myself, I only wrote down what I understood from things I read on the internet and heard in uni years ago.
pranavappu007 wrote:
Unfortunately, I can't understand even a single line in this proof.
Maths is sequential. If you lack understanding of any part, anything that comes later will also be lost to you. So just start over at the top and take in what is written there. Anyway, the maths here is not hard, but some notation is probably not well known outside of number theory circles. The | means "divides". The whole thing basically hinges on the fact that if a product divides a number, that means that both factors must divide that number. For example: 6 divides 12 (that is, 12 divided by 6 is an integer), and 6 is the product 2*3. So therefore, both 2 and 3 must divide 12, and lo is it so! I think Euclid proved that one first, and that was a couple millennia ago.
pranavappu007 wrote:
Is hardcore mathematics necessary for being a good computer programmer?
This is hardly hardcore, but you are correct, maths is only a small branch of computer science. Anyway, proofs like this actually help me understand the algorithm better, since I understand the requirements better. Why do we need d to be the multiplicative inverse of e modulo something completely separate from the modulus? Because then this whole thing works out, and otherwise it wouldn't.
pranavappu007 wrote:
As for me, I can't comprehend anything harder than 8th grade maths.
8th grade. That was where the fun started for me. Quadratic functions and how to find their zeroes. A surprising amount of use I got out of these.
As with all knowledge, maths knowledge will only help you when you have it. Only when you know certain things will you be able to apply that knowledge when you see an opportunity to do so. And maths, even pure maths like the OP in this thread, comes up surprisingly often. You want to program a SatNav? Probably need to look up Dijkstra's Algorithm. You want to do anything computer graphics related? Brush up your Algebra knowledge, cause it is about to be matrix time. Unless you're like me. I intend to create a GUI system around a quadtree. But that is some way off. Of course you can look up all these things these days, with Wikipedia being what it is, but only when you know the words to search for.
PeterX wrote:
In general I think you need to be firm in hexadecimal and bit operations etc.
Hexadecimal is merely an abbreviation for binary (hex encodes four bits per digit, octal encodes three per digit, which may be preferable if a byte encodes information in units of three bits. Lots of the x86 machine language uses octal encoding. For example, look at the operand encodings. Both ModR/M and the SIB byte consist of two three-bit fields and a two-bit one, so writing it down in octal is probably better for decoding it). On that note: Can everyone on this forum have some mercy on me, please, and no longer subject me to 64-bit constants written in binary? Thanks. I am not about to start counting the digits!
As for bit operations, yes, they are useful, and having electronics knowledge here is really useful. Do you know how many uses the humble XOR gate has? (Exclusive Or, 1-bit half adder, programmable NOT, antivalence, ...) And all of these can show up in software as well.
PeterX wrote:
For RSA obviously modulo and congruence is useful.
Yeah, that is elementary number theory. If you are into abstract algebra, look up elliptic curve cryptography. A group on top of a field!
nexos wrote:
I don't like math, and I get a long fine coding. You may have to avoid cryptography and graphics stuff, but as long as you know arithmetic, and maybe some binary math ideas, you should be good.
How do you implement your VFS? I want to use a directed graph. That requires some graph theory. In fact, I can also use graph theory to check file systems before using them. How do you store your virtual memory mappings? I will be using a self-balancing tree (not yet decided on the precise one, but red-black is apparently nicer than Anderson for this task) Binary trees, and how to balance them, is part of theoretical computer science, which is a subfield of maths, despite my joke above. At some point you will probably want to use regular expressions, and those again will require an understanding of theoretical computer science, this time of regular languages. Maths comes up more often than you think.