Number theory explained from first principles | Hacker News Reader

Number theory explained from first principles

explained-from-first-principles.com

176 pointsyewenjie29 comments

For a site literally called “Explained from First Principles”, it delves almost immediately into elliptic curve cryptography and one-way functions. Am I missing something?

Reminds me of this classic meme:

https://i.imgur.com/gAtCJFz.jpeg

Really thought your link was going to be "draw the rest of the owl"

https://i.kym-cdn.com/photos/images/newsfeed/000/572/078/d6d...

What's even funnier is that I've actually read a math textbook that quite literally did this exact thing.

90% of French technical books assume that you are an expert on the topic.

I once read some portion of a pithy textbook on Representation Theory by JP Serre. While it claimed to be an introductory book, it had the main theorem one would learn in a semester-long course on page 7, IIRC.

Textbooks should really be tested on a diverse audience with N>10, and then the feedback should be incorporated back into the text, and then another N>10 test should be done if necessary.

why? Is this because computer science text book expect you know all mathematics?

Hi, I'm the author of the article/"book" being discussed here. :-) I'm fully aware that the article isn't for everyone, but I can't see what's wrong with outlining the structure of a book in its introduction. Elliptic curves are covered in chapter 9 (out of 11). And while the first chapter is about linear one-way functions, it just motivates the rest of the article by explaining what we would like to build. Since I explain all the terms I use there (or link to Wikipedia for those who don't know, for example, what a "set" is), I can't see what's wrong with this either. But, as with any work, there are valid criticisms, of course:

- Is "number theory" an appropriate title? Should it be called "linear one-way functions explained from first principles"? Or "abstract algebra"? Or "math behind modern cryptography"? Maybe. But I think I made it quite clear in the introduction what the article is about. If you were looking for something else, feel free to leave again.

- Should I have introduced modular arithmetic and the groups of integers modulo some number before finite groups in the abstract? Maybe, but I also explain my reasoning behind this order in the introduction. As mentioned there, you get to these examples by scrolling just a bit.

It's a great article, and I've already bookmarked it to refer back to in the future whenever I need a refresher on topics I last saw in college.

I believe the confusion from the OP was that if you don't already have significant mathematical maturity (in the sense of having seen bits and pieces of number theory, linear algebra, and group theory before) you'll quickly be frustrated trying to follow along as you won't be able to reason at the necessary level of abstraction.

>Is "number theory" an appropriate title

I think "number theory from first principles" is a misleading title, and I almost skipped over it because I thought it was yet another introduction to modular arithmetic, congruences, and such. Instead, the bulk of the article lays summarizes the main results in number theory/group theory that can be put into practice to construct cryptographic primitives so I think titling it "Foundations of Cryptography" might be better.

> delves almost immediately into elliptic curve cryptography and one-way functions.

It reminds me of Kun’s primer on probability. The primer jumps to the definition of probability space and measure in the first few paragraphs: https://jeremykun.com/2013/01/04/probability-theory-a-primer...

A good primer, nonetheless. Just not necessarily accessible to majority of programmers.

That's what's lovely about mathematics- in many ways it compresses very well, assuming the receiver is infinitely intelligent. How can Alice communicate all of math to Bob? Mail him some chalk and wait!

> The primer jumps to the definition of probability space and measure in the first few paragraphs

But in a very clear and straightforward way. I think you are laughting at it a bit because you know what (and how big) a measure theory is so you are automatically 'importing' all that knowledge and you think the author did too. But all is required from the reader is literally what a finite set and a fuction are. Students are very often scared of 'big words' because it seem like it should be hard even if a simple definition of that word has just been given, which is a bit weird and I'm not sure where it's comming from

I like this approach a lot, it makes it easier learning harder and harder concepts later when you start this way because you are introduced to correct terminology early instead of analogies and hand-waving. Later material is harder to learn so analogies no longer work and it often feels like 'ok, this is too hard now' or like you are starting over

Number theory has a reputation of being a field many of whose results can be explained to the layperson.

Have you read the whole article? It's pretty good.

> Am I missing something?

Yes, the rest of the article.

Still remember the “advance calculus” book vs the “elementary set theory” in high school. To this day even though I got A in pure maths (count myself top 400 in 100,000 cohort) every time I heard the world “elementary” I shivered.

Any advanced thing no problem. Just do not start from the “first principle”. Please not. Please.

For me, "from first principles" is not the same as "elementary". It's just about "reductionism" and answering all (or at least most) "why" questions. Let me know if you find any gaps in the explanations, which make it impossible for you to follow. While I would claim that the first five chapters of the article/"book" are fairly elementary, it's in the nature of the topic that things get more and more advanced after that. (PS: I'm the author of the blog.)

Well, I like it.

Your Contributions are highly admirable and easy to summarize as you have done, Focus, Notation, Intuition, and Completeness are major milestones on their own and I don't even experience the Interactivity on my browser.

I also agree with some of the other commenters who say the reader should already have more than just a bit of exposure to number theory beforehand, developing understanding of more introductory applications would be good and could probably be chosen to provide a particularly firm foundation for the march toward cryptography which gets quite advanced quite quickly.

Next, you might want to draft what could be considered a prerequisite text of your own for this masterpiece so the less initiated can get up to speed and get the most out of it. Also, I suppose your next two articles will be further advanced and could be easier to grasp for those who first have better understanding of what you have now.

Have a look at https://explained-from-first-principles.com/number-theory/to... for the interactivity. :-)

To me, "from first principles" implies a certain presentation style that's different than what this article employs. It feels like you take it to mean "start from the axioms and build up without any gaps or unanswered whys" which is fine, but it turns into a laundry-list of topics the reader needs to get through before seeing the payoff, which in a way is no different from any other math text. I was expecting a more reverse-engineering approach where the first principles are derived from analysis of the problem / application, and we proceed from there.

Yup. Just buying and using a spoon is trivial, but building one from “first principles” is 1,000x harder.

>The goal of this article is to understand how we can construct linear one-way functions using finite groups which have a certain property.

What is linear? What is one-way? What is a function? What is a finite group? What is a property?

The inline links are bandages.

As the title before this very sentence says, this is the outline of the whole article/"book". Since it is a web page, I link to the corresponding chapter instead of mentioning the page number. The very first chapter starts with explaining what a function is and what I mean by "one-way" and "linear". If this is beyond your attention span, then this article isn't for you. (PS: I'm the author of the article. I'm also aware that it's difficult to get an overview on mobile, so I'd suggest reading the article on a laptop or tablet.)

Those are all explained in the article. This sentence describes what you will understand by the end.

these are pretty elementary in the grand scheme of things!

Sure but are they the foundational elements of number theory? lol

Very cool.

I'd also recommend Number Theory by Andrews. It's a great comprehensive introduction.

Very dry! Was hoping for first principles, the way a Thomist would start at the smallest element in the conversation, like God, and then expand outwards in a steady flow.

The first principles here are just a book of proven theories. It doesn't start anywhere, you just jump into knowing dry maps of theory. Flow is non-existant.

Reply on news.ycombinator.com