You need a full jury to conclude a number is a prime, whereas even just one dissenter will show the number is composite. This implies that primes are guilty and composites are innocent. This makes sense, because we usually assume numbers are composite until proven prime.
You forgot to mention how ugly prime numbers are. We all know that 13 and 17 cannot even compare with the beauty and structure such as 36 and 100. The worst are those large primes like 101 or 83. WHY CAN'T THEY GROW UP LIKE EVERYONE ELSE? THEY LACK SOPHISTICATION AND ARE A SHAME TO THIS WORLD. AND DON'T CLAIM IT'S BECAUSE OF THE WAY THEY ARE TREATED. IT'S THE NATURE OF THEIR EXISTENCE THAT IS THE PROBLEM. WHY ARE THEY CALLED PRIME WHEN THEY ARE USELESS, SINFUL REINCARNATIONS OF THE DEVIL HIMSELF.
@@ivarangquist9184 True mathematical beauty lies in the primes. Any composite order you cherish seems boring and daft in comparison to the primes' unruly yet reliable nature.
I first learned about this when I took a class taught by Prof. Rabin, who called it the "randomized primality test" because he was too humble to tell us it was named after him, which made it a bit hard to find references to what he was talking about in our textbook or online
@@will1603 i mean it was a class taught in my school's CS department while i was working towards a CS degree there. maybe math students or something would've also been welcome (i don't remember, it was a long time ago), but it wasn't like totally something completely, um, randomized
55,648 is the 50,000th composite number. I ran the script for each number between 2 to 55,648. Runtime: ~27 minutes on my machine. The numbers which turned up to be false-witnesses the most times were: (The number, how many times found lying) (2401, 183) (625, 182) (6561, 173) (529, 166) (81, 164) (729, 152) (4096, 149) (4225, 126) (3481, 125) (256, 123) Nice to see that these biggest liars are all (almost) powers of primes: 2401 =7 ^ 4 625 =5 ^ 4 6561 =3 ^ 8 529 =23 ^ 2 81 =3 ^ 4 729 =3 ^ 6 4096 =2 ^ 12 4225 =65 ^ 2
They are all perfect squares: 49^2, 25^2, 81^2, 23^2, 9^2, 27^2, 64^2, 65^2, 59^2, 16^2 ... also, taking powers of 4 rather than perfect squares, there is 3,4,5,7,8,9 (6 is missing; did 1296 not quite make the cut)? Meanwhile, 23, 59 and 65 seem quite random relative to the others. If I was to try to screw around with it, I would notice that 65 is 23*3-1, I would note that 59 = 23 + 36, and 65 = 23 + 42. I'm not sure this would get me anywhere :)
Previous statements I made were incorrect, due to hasty coding. I am very confident in the following results: For 2 < n < 100, n is odd, the top 5 naughtiest numbers are the following: 38, with 4 offences 8, with 3 offences 18, with 3 offences 34, with 3 offences 47, with 3 offences For 2 < n < 1000, n is odd, the top 5 naughtiest numbers are the following: 64, with 16 offences 68, with 15 offences 118, with 14 offences 307, with 14 offences 274, with 13 offences For 2 < n < 10000, n is odd, the top 5 naughtiest numbers are the following: 512, with 68 offences 64, with 66 offences 256, with 59 offences 1451, with 58 offences 254, with 57 offences There seems some justification that powers of two are particularly naughty.
11:53 "Over 8 times as far" must of course be referring to a 'Parker 8', which we can therefore infer is some value less than 6.6103. We learn so much from Matt!
At one point (7:02) he also said that 18 is just below a quarter of 90 - and I was like "WTF, 90/18=5, Matt surely knows that", but, just like with what you wrote, in this case it must have been a Parker quarter. Okay, hold up. I've just watched it again to find the timestamp and he said "quarter" because 25% is the worst-case scenario for the ratio of liars.
The results are symmetrical, so the witness "a" always gives the same results as witness (n-a), so the 18 liars for 91 are actually: 1,9,10,12,16,17,22,29,38,(91-38),(91-29),(91-22),(91-17),(91-16),(91-12),(91-10),(91-9),(91-1) You can also use witnesses a>n without problems, but the result for a, a+n, a+2n, a+3n ... etc. will be the same.
@@Falanwe Yeah I know, I forgot to mention that. I just added them in the list because they were shown in the video for the 91 case. You should also never use n, 2n, 3n, ... etc as witness, they will always show composite even for primes. So basically (2 to n-2), (n+2 to 2n-2), (2n+2 to 3n-2), ... etc. are ok, but the results for each range are identical, but it is useful to use a>n if you have a huge a that works for a lot of n. For example the 2 witnesses a=336781006125 or a=9639812373923155 will work for n
If anyone is interested, this is how you'd implement it in c# public static int Pow2(int x, int y, int z) { int number = 1; for(int i = 0; i < y; i++) { number = number * x % z; } return number; }
This is basically a generalization of the Fermat primality test, where you just test if a^(n-1) = 1 (mod n); if it isn't, then it's definitely composite, but if it is, then it's only probably prime. Except, for the Fermat test, there are "Carmichael numbers" for which every witness is a liar; the first three are 561, 1105, and 1729. So the real innovation of the Miller-Rabin test is being able to prove that at most 25% of its witnesses are liars, enabling an effective probabilistic test.
This reminds me of bloom filters and their cousins, the xor and fuse filters. They are constructed from a set of numbers (hashes, usuallly) but they use far fewer bits than the set and can tell you if a number isn't in the set faster than you could search the set. You can control how often they lie about it being in the set by the size of the filter in relation to the size of the set. Since these filters are just big integers, there should be naturally occurring filters for every possible set somewhere in the natural numbers.
@@Embermeetstimber Maybe, but if you think about it too much, you will be relieved when an infinite troupe of monkeys shows up at your door wanting to talk to you about the script for Hamlet they've worked out.
Wow. I'm studying computer science. I just found this exact thing in a footnote of one of my scripts (discrete mathematics). We were looking at groups, modular arithmetic and primes to understand RSA public-key encryption . This is just checking weather 1 is the greatest common divisor of a and n. If you check all possible dividers you will know wether it's prime. Well that and some awesome aspects of mathematics that keep computation feasible. We used it because a gcd of 1 is necessary for it to have an inverse in the groups we were using, breaking group axioms, so we'd either have to exclude them or just use a prime which had non of them (except for 0 which is equal to n). Damn this feels amazing understanding the math behind this.
The funny thing is, that meme became popular when a UA-cam video of the clip went viral. That clip was uploaded by the user Tibees, who ended up becoming a math UA-camr. It's full circle.
matt, that calculator has a FACT button on it. ttype the number, hit equals, then shift+(the degrees button) and it prints out the prime decomposition of the number
I programmed my TI-84 CE to factor any number under 2.52 million in November 2020. :) Why that number? Cos the device runs out of memory beyond 2.5 million. I even came up with an estimated calculation time (3 minutes for factoring the largest numbers). Have you ever programmed your calculator Matthew in TI Basic?
@@ZedaZ80 Yes, the calculator in the video was a Casio. I used to own a Casio a long time ago, but sadly most textbooks here in the US require Texas Instruments. :( At least I can program it.
I'm a little bit curious whether 1662803 has any particular properties that makes it more likely to be honest, or if it's just a pure numerical coincidence that it happens to cover up the holes of the other three numbers over that range.
@@volodymyrgandzhuk361 Ah, lay off. Ever since the Parker Square plenty of almost correct things have been labelled as Parker solutions and Matt's in on the joke. He is a stand-up comic you know
"Minimizing the mistakes, not eradicating but cutting back" (1:50) is henceforth known as the Parker Method. The Parker Method gave us the Parker Square.
If the set of witnesses are the first n primes, what is the largest number that can be conclusively confirmed or rejected as prime, as a function of n? The examples Matt showed makes me think it might be exponential or double exponential.
8:29 This kind of thing is how you know it's Parker. In truth, only the first modular comparison is allowed to yield a remainder of +1 for a primality verdict. If the first test is not +-1 and a later test is +1, a is a witness to n.
so I did the math and from all the odd numbers from 7 to 25326001 I found that: 2 give false testimony to 255 numbers 3 give false testimony to 314 numbers 5 give false testimony to 280 numbers
With the way you explained the algorithm, the strongest liars would be 1 and (n-1). They lie for ALL non-primes. Which is exactly why the correct algorithm excludes them from the list of possible candidates
@@Anonymous-df8it Well, 1 will always stay 1, no matter to which power you raise it. And (n-1) mod n is the same as -1, so it will be either 1 or -1 (mod n) when you raise it to any positive power. Those are exactly the "probably prime" results the algorithm is looking for, so using those will result in a false positive every time.
@@Anonymous-df8it I have not tried to find that out yet, but some others in the comments have listed their results. Though the last time I checked only up to 100.000. You probably need a lot of calculations to go higher since you have to check n-3 numbers every time. So the algorithms time increases quadratically...
Interestingly I can’t seem to find anything breaking down what the “strongest liars” are. My intuitive guess is the smaller the number the better the chance it lies so 2 might be the strongest, but I’m curious to see an answer to that question Matt had at the end.
@@keithbromley6070 star witnesses are only reliable if you query the whole group - it could be that 2 only covers 3's weaknesses but lies all the other times. Just a possibility, no idea if it's true but saying you can be a star witness and a frequent liar!
Though not quite the same, one probabilistic primality test I like is the Fermat primality test - it's kind of like a worse version of the Miller-Rabin primality test. It builds on Fermat's Little Theorem and states that if a^(p - 1) ≡ 1 (mod p) with 1 < a < p - 1, then p is probably prime. And if the congruence doesn't hold for a given a, then p is composite. However, there is a class of numbers where ALL coprimes of a between 1 and p - 1 are congruent to 1 (mod p) even though p is composite. These are known as Carmichael Numbers, and the smallest is 561 = 3 * 11 * 17. Indeed, the test only fails if a is set to one of its factors (which you can trivially divide p by to confirm it's compositeness).
May I just interject a comment, please? I just adore Numberphile Matt and this channel. It is always fascinating beyond words, and exceptionally educational. Bravo, Numberphile! Superb content!
16:45 Matt being super happy about 747 appearing, looking up at the camera all enthusiastic, and then realizing nobody in the room shares his level of number geekhood. This is me about 5 times every day. 🤣
The witness is providing an alibi for the number m. If m has an alibi (i.e., mod =1), he's not the thief (not prime). Not having an alibi doesn't make m the thief, call another witness to the stand.
Also, for smaller numbers (like, 91), you can call over 1/4 of all witnesses (like, a half); and, if all of them say it’s prime, it’s definitely prime. Of course, it won’t work for bigger numbers (like, a trillion); so, for those, you’d better call up the star witnesses.
What i like most about Brady's style of interviewing is, that it is on such a personal level. Also for example when he says "Brilliant, they are great people"
His upset sigh when he was told right away that 747 is indeed not prime… It’s a relatable feeling. Today I was counting primes from 1000 out of boredom, until I got to above 2000 and said “why not”. Sad that 2023 isn’t prime, but 2027 is, so we still have a few more years to go.
23³⁷³ mod 747 is actually not too bad by hand even. You don't need to do 373 calculations, just 23, at which point you're back at where you started. Then you just need to use a single modulus operation to figure out which number in the cycle you will get out at the end.
Off the top of my head, I wouldn't be surprised to see the strongest liar change as you test higher and higher numbers. For example: testing liars for all numbers up to 1001, you can't have 1001 having witnessed yet. But it could, by the time you've tested up to a million, be the strongest liar.
Are these star numbers found by checking every number up to the limit and seeing that they do not lie for any or is there a proof that gives this limit without having to check? I'm assuming the former but would be cool to know.
Judge : 4 was found guilty and is sentenced to become a part of Collartz Conjecture loop. Lawyer : But almost all of the witnesses says 4 isn't guilty! Judge : But 1662803, 23, 13, and 2 said that he is guilty!
The 4^-k probability of falsely declaring a number prime is a very pessimistic one as the number being tested gets bigger and the number of witnesses increases. And if you're worried, then iterate for 25 or 50 different witnesses. It's a sufficiently fast algorithm that you can afford to do that even for RSA-sized primes - 800 decimal digits or so - if you don't mind waiting a few milliseconds. Also, you can tweak Miller-Rabin to sometimes get a prime factor out of a number in addition to proving its compositeness.
Apparently around 4 or 5 random tests is sufficient. 1/4 liars is an upper bound and when dealing with cryptographic sized numbers it's actually far less. So in practice my intuition to do like you say k of 50 or 100 is no needed at all. Although your choices must be random.
Question: when using the “star witness” approach, which is more, start testing with the lower numbers first, the higher numbers first, or is there no difference?
Note that the value can be + or - 1 ONLY for the lowest check where the 2 exponent is zero and it's just a^d mod n, for all the higher values (a^(d*2^r) mod n) the solution has to be negative one. Otherwise you'll get false primes much earlier, such as 1729 and 2465 when checking with 2 and 3.
This looks very similar to Fermat's Little Theorem, I can't remember whether Numberphile's ever done a video on the topic but some other channels definitely have (I'd recommend Mathologer's)
The way the test is described in the video, it fails for Fermat primes like 257. When you subtract 1 and take out the 2s from what's left, the d value just becomes 1, so very few witnesses will yield a remainder of +-1 even though the test number is prime. It also fails for primes lying above multiples of large powers of 2, such as 193, where d becomes 3. For instance, with a witness of 3, of course its cube (27) is not +-1 (mod 193), so the supplemental task starting at 8:08 is necessary rather than optional.
Something that wasn’t said in the video is that there’s a number that’s trivially always a strong liar if the number isn’t prime: 1, because 1 to the power of anything is 1, which is congruent to 1 modulo anything. 1 is the kind of witness who just wants to get out of the courtroom ASAP, so it’ll accuse anyone on the stand and leave.
I loved "primey". People assume that it's a strict primality test, but actually from a non-subjective viewpoint it's more like a big ball of wibbly-wobbly primey-wimey stuff.
Well first of Mersenne numbers have their own primality test which only works for them and is much more efficient than this one. Also 2 is a liar for all Marsenne Numbers (and all Fermat Numbers), using this test with 2 will same Prime for all Marsenne Numbers, whether prime or composite
These witnesses have had a very interesting career. They randomly fly from being witnesses, to investigators to jurors. They really don't play by any one's rules.
You need a full jury to conclude a number is a prime, whereas even just one dissenter will show the number is composite. This implies that primes are guilty and composites are innocent. This makes sense, because we usually assume numbers are composite until proven prime.
Elegant.
But the star witnesses you have to call in are the most notorious primes. It takes a hardened criminal to rat out their fellow criminals.
You forgot to mention how ugly prime numbers are. We all know that 13 and 17 cannot even compare with the beauty and structure such as 36 and 100. The worst are those large primes like 101 or 83. WHY CAN'T THEY GROW UP LIKE EVERYONE ELSE? THEY LACK SOPHISTICATION AND ARE A SHAME TO THIS WORLD. AND DON'T CLAIM IT'S BECAUSE OF THE WAY THEY ARE TREATED. IT'S THE NATURE OF THEIR EXISTENCE THAT IS THE PROBLEM. WHY ARE THEY CALLED PRIME WHEN THEY ARE USELESS, SINFUL REINCARNATIONS OF THE DEVIL HIMSELF.
@@ivarangquist9184
I see that the spirit of Pythagoras lives well & strong inside you, my child
@@ivarangquist9184 True mathematical beauty lies in the primes.
Any composite order you cherish seems boring and daft in comparison to the primes' unruly yet reliable nature.
I first learned about this when I took a class taught by Prof. Rabin, who called it the "randomized primality test" because he was too humble to tell us it was named after him, which made it a bit hard to find references to what he was talking about in our textbook or online
Thats cool
That is COOOOOOOOOLLLL
Taught by the one who made it XD
I love how in america you can just choose to take a class. One of the few things from America id like in theuk
@@will1603 i mean it was a class taught in my school's CS department while i was working towards a CS degree there. maybe math students or something would've also been welcome (i don't remember, it was a long time ago), but it wasn't like totally something completely, um, randomized
55,648 is the 50,000th composite number.
I ran the script for each number between 2 to 55,648. Runtime: ~27 minutes on my machine.
The numbers which turned up to be false-witnesses the most times were:
(The number, how many times found lying)
(2401, 183)
(625, 182)
(6561, 173)
(529, 166)
(81, 164)
(729, 152)
(4096, 149)
(4225, 126)
(3481, 125)
(256, 123)
Nice to see that these biggest liars are all (almost) powers of primes:
2401 =7 ^ 4
625 =5 ^ 4
6561 =3 ^ 8
529 =23 ^ 2
81 =3 ^ 4
729 =3 ^ 6
4096 =2 ^ 12
4225 =65 ^ 2
thats so cool. i wonder why that is.
They are all perfect squares: 49^2, 25^2, 81^2, 23^2, 9^2, 27^2, 64^2, 65^2, 59^2, 16^2 ... also, taking powers of 4 rather than perfect squares, there is 3,4,5,7,8,9 (6 is missing; did 1296 not quite make the cut)? Meanwhile, 23, 59 and 65 seem quite random relative to the others. If I was to try to screw around with it, I would notice that 65 is 23*3-1, I would note that 59 = 23 + 36, and 65 = 23 + 42. I'm not sure this would get me anywhere :)
How you did the test with an even number
@@talastra welp guess I'm not trusting squares then
Yeah, don't trust anyone over 30@@therealelement75
"Well I happen to know, below 91 there are 90 numbers"
The things I learn from Numberphile are priceless.
*negative numbers and zero*: "Are we a joke to you?"
@@raphaelschmitz-dumont4426 The rationals: "Are we a joke to you?"
@@OrangeC7 The irrationals: "Are we a joke to you?"
@@timallgood4108 the complex:" hey look over there!"
@@Ludwig-MariaAKern-yz2vs unfortunately, the complex are neither below nor over 90, afaik.
Previous statements I made were incorrect, due to hasty coding. I am very confident in the following results:
For 2 < n < 100, n is odd, the top 5 naughtiest numbers are the following:
38, with 4 offences
8, with 3 offences
18, with 3 offences
34, with 3 offences
47, with 3 offences
For 2 < n < 1000, n is odd, the top 5 naughtiest numbers are the following:
64, with 16 offences
68, with 15 offences
118, with 14 offences
307, with 14 offences
274, with 13 offences
For 2 < n < 10000, n is odd, the top 5 naughtiest numbers are the following:
512, with 68 offences
64, with 66 offences
256, with 59 offences
1451, with 58 offences
254, with 57 offences
There seems some justification that powers of two are particularly naughty.
Can't wait for the next video on N*ughty Numbers
I wonder if it's because they're a power of 2. Who was second and third for each test respectively?
81 seems naughty for all natural up to thousands.
I think it's interesting that these are powers of two. Thanks for this!
I wonder if this is an actual patten and if that's been proven already... 🤔
There is a lot of character in this video, well done to both of you.
New to numberphile, eh? 😄
Yeah, really made me invested in the plot of this crime drama.
welcome to the wonderful world of matt parker
@@toolebukk he is punning around...
@@katowo6521 berbahasa indonesia
11:53 "Over 8 times as far" must of course be referring to a 'Parker 8', which we can therefore infer is some value less than 6.6103.
We learn so much from Matt!
At one point (7:02) he also said that 18 is just below a quarter of 90 - and I was like "WTF, 90/18=5, Matt surely knows that", but, just like with what you wrote, in this case it must have been a Parker quarter.
Okay, hold up. I've just watched it again to find the timestamp and he said "quarter" because 25% is the worst-case scenario for the ratio of liars.
Similar to the 'Parker Quadrillion' at 12:49 eh?
false.
13:03 Matt's about 3 orders of magnitude off; it's 1 trillion and 122 billion. That's a real Parker Quadrillion if I've ever seen one
Gotta have at least one per video
The billion is sus.
I'm pretty sure he puts them in intentionally, like his book
Could be the British Vs American definition.
@@markinnes4264 No-one uses the Long-count any more in mathematics
"Witness, is this number prime?"
"Yes!"
"Objection, your honour. We have evidence that this witness is a strong liar."
"Sustained."
A Parker witness, you might say.
@@qovro uh oh
he gave it a go, but wasn't quite right.
Oh no
SUS
I love these little anthropomorphisations of numbers and the stories of their relations :)
I prefer onomatopoeic anthropomorphisations
Ooh I'd love it if they got together with ViHart and did a story series of different number types. The only question left is what should they call it?
Hmmm
I'm ALWAYS team anthro! In fact, I dislike strongly when anybody tries to stop me from anthroing for a bit of spice.
Love your pfp
I love how the numbers changed from witnesses to detectives to cops to juries as the video progressed XD
Yeah, the story did seem somewhat judicially confused...
That's OK though, it makes for really interesting worldbuilding.
Spoiler alert : one of them is the killer.....
Detectives and cops can be witnesses, no? The only real jump was to jury.
Matt liked the numbers so much, that he kept promoting them.
The results are symmetrical, so the witness "a" always gives the same results as witness (n-a), so the 18 liars for 91 are actually:
1,9,10,12,16,17,22,29,38,(91-38),(91-29),(91-22),(91-17),(91-16),(91-12),(91-10),(91-9),(91-1)
You can also use witnesses a>n without problems, but the result for a, a+n, a+2n, a+3n ... etc. will be the same.
Coolio
Cool, so if I wanted to figure out all liars for any given number I'd only have to check halfway.
You should never call 1 and n-1 as witnesses: they will always tell you n is prime.
@@Falanwe Yeah I know, I forgot to mention that. I just added them in the list because they were shown in the video for the 91 case. You should also never use n, 2n, 3n, ... etc as witness, they will always show composite even for primes. So basically (2 to n-2), (n+2 to 2n-2), (2n+2 to 3n-2), ... etc. are ok, but the results for each range are identical, but it is useful to use a>n if you have a huge a that works for a lot of n.
For example the 2 witnesses a=336781006125 or a=9639812373923155 will work for n
@@Einyen Thanks for the information. You rock.
Absolutely admire the strength of Parker to not make a “Prime Suspect” joke in the whole video haha
It's like they say: Don't do the crime if you can't prove you're prime.
Awesome one! 🤣🤣🤣
This comment is on fire 🔥
@@samuelvilz then get some water
I had a lecturer who would pronounce "prime" as "crime"
false.
I was waiting for this for about 500years!
😆 well look who it is!
Is the comment to the video too small to put proof in?
@@volodyadykun6490 Unfortunately, yes.
Time Lord!
Pierre! How’s it hangin? How’s the dirt nap? Did you dream of Bernhard Riemann?
* ponts at 747 *
"we're assuming this is odd"
One of the boldest assumptions a mathematician has ever said
The 747 airplane is kinda odd. It has a hump like a giant metal sky whale. It is my favorite mainstream aircraft though. :)
@@thatguyalex2835 The hump is why I love the old Antonov's.
It's a Parker conjecture.
@@SwervingLemon I like both models of planes. Are you talking about the AN-225?
Makes sense that the primes are the most apt witnesses for telling if another number is prime or not.
It takes one to know one
They see each other at the various prime meetings and functions.
??
Python's pow function takes an optional mod argument, making this test easy to program. For instance, pow(23, 373, 747) = 131.
Huh, did not know that!
How sensible for anyone programming any cryptographic stuff.
I think I'm going to have to start solving my project euler problems in python due to this lol
If anyone is interested, this is how you'd implement it in c#
public static int Pow2(int x, int y, int z)
{
int number = 1;
for(int i = 0; i < y; i++)
{
number = number * x % z;
}
return number;
}
@@1992jamo Try:
while (y > 0) {
if (y & 1) number = number * x % z;
x = x * x % z;
y >>= 1;
}
instead.
Matt Parker and James Grime, really the two stars you need on the 10th anniversary of Numberphile
Don't forget Cliff Stoll!
And Hannah Fry!
Neil (what was his surname again... the OEIS founder) and Ben Sparks are also people I like to see in these videos!
This is basically a generalization of the Fermat primality test, where you just test if a^(n-1) = 1 (mod n); if it isn't, then it's definitely composite, but if it is, then it's only probably prime. Except, for the Fermat test, there are "Carmichael numbers" for which every witness is a liar; the first three are 561, 1105, and 1729. So the real innovation of the Miller-Rabin test is being able to prove that at most 25% of its witnesses are liars, enabling an effective probabilistic test.
Fun that Ramanujan's Number is in there
This reminds me of bloom filters and their cousins, the xor and fuse filters. They are constructed from a set of numbers (hashes, usuallly) but they use far fewer bits than the set and can tell you if a number isn't in the set faster than you could search the set. You can control how often they lie about it being in the set by the size of the filter in relation to the size of the set. Since these filters are just big integers, there should be naturally occurring filters for every possible set somewhere in the natural numbers.
Sounds very Miller-Rabin-y.
@@Embermeetstimber Maybe, but if you think about it too much, you will be relieved when an infinite troupe of monkeys shows up at your door wanting to talk to you about the script for Hamlet they've worked out.
??
Wow. I'm studying computer science. I just found this exact thing in a footnote of one of my scripts (discrete mathematics). We were looking at groups, modular arithmetic and primes to understand RSA public-key encryption
. This is just checking weather 1 is the greatest common divisor of a and n. If you check all possible dividers you will know wether it's prime. Well that and some awesome aspects of mathematics that keep computation feasible. We used it because a gcd of 1 is necessary for it to have an inverse in the groups we were using, breaking group axioms, so we'd either have to exclude them or just use a prime which had non of them (except for 0 which is equal to n). Damn this feels amazing understanding the math behind this.
"The numbers don't lie." - "Well actually they do!"
When I heard "In the future, entertainment will be randomly generated." I didn't think numbers would be this entertaining.
Numbers can lie- I mean
WEED EATER
i mean, is entertainment not randomly generated anyway?
Wait youre the chess guy
The funny thing is, that meme became popular when a UA-cam video of the clip went viral. That clip was uploaded by the user Tibees, who ended up becoming a math UA-camr. It's full circle.
Same
matt, that calculator has a FACT button on it. ttype the number, hit equals, then shift+(the degrees button) and it prints out the prime decomposition of the number
I programmed my TI-84 CE to factor any number under 2.52 million in November 2020. :) Why that number? Cos the device runs out of memory beyond 2.5 million. I even came up with an estimated calculation time (3 minutes for factoring the largest numbers).
Have you ever programmed your calculator Matthew in TI Basic?
@@thatguyalex2835 So you're saying it can do FACTs and Logic?
@@thatguyalex2835 friend, that's a Casio
@@U014B Nope. :) It can't. It is not a Casio.
@@ZedaZ80 Yes, the calculator in the video was a Casio. I used to own a Casio a long time ago, but sadly most textbooks here in the US require Texas Instruments. :( At least I can program it.
I'm a little bit curious whether 1662803 has any particular properties that makes it more likely to be honest, or if it's just a pure numerical coincidence that it happens to cover up the holes of the other three numbers over that range.
Well 1662803 is prime and 1662804 is very composite.
Why am I not suprised that you'd be thinking about something like that :D But it's definetly interesting
Pretty sure "happens to cover up the holes of the other three numbers over that range"
@@DukeBG my guess as well
They were just raised not to be a liar.
"747 has been charged with homicide and vehicular manslaughter and will be serving 747 years in prison"
“I happen to know that below 91 there are 90 numbers”. Excellent
This comment is definitely perfect
18/90 is the new Parker approximation for 1/4
He said AT MOST 1/4 of the numbers are liars
@@volodymyrgandzhuk361 Ah, lay off. Ever since the Parker Square plenty of almost correct things have been labelled as Parker solutions and Matt's in on the joke. He is a stand-up comic you know
@@volodymyrgandzhuk361 So let's hope for him that there are no composite numbers n = p*q*r where each of the prime number q, and r divide (n-1)/2.
I saw 91 and something in my brain immediately said “it’s 70 plus 21 so 7 times 13”
"Minimizing the mistakes, not eradicating but cutting back" (1:50) is henceforth known as the Parker Method. The Parker Method gave us the Parker Square.
I gotta agree; it’s pretty cool to be able to infer primality or compositness without actually doing any division!
If the set of witnesses are the first n primes, what is the largest number that can be conclusively confirmed or rejected as prime, as a function of n? The examples Matt showed makes me think it might be exponential or double exponential.
that sounds pretty interesting
8:29 This kind of thing is how you know it's Parker. In truth, only the first modular comparison is allowed to yield a remainder of +1 for a primality verdict. If the first test is not +-1 and a later test is +1, a is a witness to n.
so I did the math and from all the odd numbers from 7 to 25326001 I found that:
2 give false testimony to 255 numbers
3 give false testimony to 314 numbers
5 give false testimony to 280 numbers
This is the maths video with the most plot twists I've ever seen
13:03 that’s a blunder if I’ve ever seen one, classic Matt Parker move.
11:50 Another blunder
This is great, I had learnt Miller Rabin test in my Cryptography class, but not so clearly with these Witness numbers.
Professor: The test isn’t even that hard
The test:
Question 1: Guess the next number in the following sequence:
2, 13, 23, …?
687. That's my guess. Therefore I've done what you asked. Full marks, please!
Liar numbers should be called “perjurious numbers”! 😂
Because, if there's one things mathematicians like, it's giving catchy names to numbers.
never call 1 to the stand, it always gives 1
Ooh. Actually throwing in the "Dun Dun"
I feel like some aggressive content ID would try to claim the whole video over those .5 seconds
Hi Verlis didn’t expect to see you here lol
I know this is unrelated to your comment but can I say how cool your profile picture looks?
It looks really nice.
I think it's insufficient for a legal claim.
@@Qermaq
The bots aren’t smart enough to know that
@@executeorder6613 Yeah but the bots aren't asked to match stuff like this.
With the way you explained the algorithm, the strongest liars would be 1 and (n-1). They lie for ALL non-primes. Which is exactly why the correct algorithm excludes them from the list of possible candidates
Proof?
@@Anonymous-df8it Well, 1 will always stay 1, no matter to which power you raise it. And (n-1) mod n is the same as -1, so it will be either 1 or -1 (mod n) when you raise it to any positive power. Those are exactly the "probably prime" results the algorithm is looking for, so using those will result in a false positive every time.
@@holgerchristiansen4003 What would be the next strongest liars?
@@Anonymous-df8it I have not tried to find that out yet, but some others in the comments have listed their results. Though the last time I checked only up to 100.000. You probably need a lot of calculations to go higher since you have to check n-3 numbers every time. So the algorithms time increases quadratically...
@@holgerchristiansen4003 Why quadratically? Wouldn't that make it run exponentially with the number of digits?
Your Quadrillion is missing 3 digits.
Interestingly I can’t seem to find anything breaking down what the “strongest liars” are. My intuitive guess is the smaller the number the better the chance it lies so 2 might be the strongest, but I’m curious to see an answer to that question Matt had at the end.
That makes sense.. it would seem 2 would lie half the time. This is just my guess, though.
2 is the best witness yet the strongest liar lol
Surely not 2? It was part of all the star witness groups! Perhaps the lowest non-prime? Dastardly number 4.
@@keithbromley6070 star witnesses are only reliable if you query the whole group - it could be that 2 only covers 3's weaknesses but lies all the other times. Just a possibility, no idea if it's true but saying you can be a star witness and a frequent liar!
@@AdamHill42 I guess I don’t understand it enough to be sure either way!
Though not quite the same, one probabilistic primality test I like is the Fermat primality test - it's kind of like a worse version of the Miller-Rabin primality test. It builds on Fermat's Little Theorem and states that if a^(p - 1) ≡ 1 (mod p) with 1 < a < p - 1, then p is probably prime. And if the congruence doesn't hold for a given a, then p is composite.
However, there is a class of numbers where ALL coprimes of a between 1 and p - 1 are congruent to 1 (mod p) even though p is composite. These are known as Carmichael Numbers, and the smallest is 561 = 3 * 11 * 17. Indeed, the test only fails if a is set to one of its factors (which you can trivially divide p by to confirm it's compositeness).
One of the best numberphile videos I have seen!! Well done to both of you.
That's a very Parker Prime Number test!
You two really had a lot of fun in this episode. Well done!
13:06 the number jumps from trillions to millions, I want justice for my boys the billions digit
Having not looked into the numbers most prone to lying, my first instinct would be that it'd likely be related to the highly composite numbers.
May I just interject a comment, please? I just adore Numberphile Matt and this channel. It is always fascinating beyond words, and exceptionally educational. Bravo, Numberphile! Superb content!
I love the 12 Angry Men reference.
THANK YOU for finally covering Miller Rabin! I've always been fascinated with this particular primality test due to how incredibly simple it seems.
16:45 Matt being super happy about 747 appearing, looking up at the camera all enthusiastic, and then realizing nobody in the room shares his level of number geekhood. This is me about 5 times every day. 🤣
you meant 14:14 ?
I loved this video and love matt parker. Great
The witness is providing an alibi for the number m. If m has an alibi (i.e., mod =1), he's not the thief (not prime). Not having an alibi doesn't make m the thief, call another witness to the stand.
*mod ≠ ±1
Also, for smaller numbers (like, 91), you can call over 1/4 of all witnesses (like, a half); and, if all of them say it’s prime, it’s definitely prime. Of course, it won’t work for bigger numbers (like, a trillion); so, for those, you’d better call up the star witnesses.
A Numberphile Classic!
What i like most about Brady's style of interviewing is, that it is on such a personal level. Also for example when he says "Brilliant, they are great people"
That's a nice Casio, Matt. Can we get a review?!
His upset sigh when he was told right away that 747 is indeed not prime… It’s a relatable feeling.
Today I was counting primes from 1000 out of boredom, until I got to above 2000 and said “why not”. Sad that 2023 isn’t prime, but 2027 is, so we still have a few more years to go.
advanced congrats 4mil subs numberfile!
”10^45 is gonna be a very big number.” Yeah, it is. Heptilliard, to be precise :D.
Quddarodecillion
@@windowsuranusSP5 I’m doing ”the long system”, a.k.a. *_THE_* System.
Such a cool concept. Those unreliable witnesses...🤣
As soon as I saw the title I knew this would be the Miller-Rabin test; I just happened to be working with it last week
cant wait for the parker square numbers
23³⁷³ mod 747 is actually not too bad by hand even. You don't need to do 373 calculations, just 23, at which point you're back at where you started. Then you just need to use a single modulus operation to figure out which number in the cycle you will get out at the end.
Off the top of my head, I wouldn't be surprised to see the strongest liar change as you test higher and higher numbers. For example: testing liars for all numbers up to 1001, you can't have 1001 having witnessed yet. But it could, by the time you've tested up to a million, be the strongest liar.
Well, 1 is the strongest liar of all, because 1^a = 1 (mod n) for any numbers a and n.
M.C Escher print on the wall! Nice!
Are these star numbers found by checking every number up to the limit and seeing that they do not lie for any or is there a proof that gives this limit without having to check? I'm assuming the former but would be cool to know.
we need more Matt again :)
Judge : 4 was found guilty and is sentenced to become a part of Collartz Conjecture loop.
Lawyer : But almost all of the witnesses says 4 isn't guilty!
Judge : But 1662803, 23, 13, and 2 said that he is guilty!
This video made me so happy. It is so much fun
Hey Numberphile I love the channel. Is there a chance you could do a video on celestial navigation?
Lawyer by trade, numberphile by hobby. This is SO up my alley.
Excellent video, funny, interesting, well edited. 10/10.
"2, forget about 3, 13, 23, and the team captain; 1,662,803."
That had me dying because I was not expecting the last number to be so f*cking large.
The 4^-k probability of falsely declaring a number prime is a very pessimistic one as the number being tested gets bigger and the number of witnesses increases. And if you're worried, then iterate for 25 or 50 different witnesses. It's a sufficiently fast algorithm that you can afford to do that even for RSA-sized primes - 800 decimal digits or so - if you don't mind waiting a few milliseconds. Also, you can tweak Miller-Rabin to sometimes get a prime factor out of a number in addition to proving its compositeness.
Apparently around 4 or 5 random tests is sufficient. 1/4 liars is an upper bound and when dealing with cryptographic sized numbers it's actually far less. So in practice my intuition to do like you say k of 50 or 100 is no needed at all. Although your choices must be random.
9:55 ”If they *_COSINE”_* 🙃
Question: when using the “star witness” approach, which is more, start testing with the lower numbers first, the higher numbers first, or is there no difference?
Note that the value can be + or - 1 ONLY for the lowest check where the 2 exponent is zero and it's just a^d mod n, for all the higher values (a^(d*2^r) mod n) the solution has to be negative one. Otherwise you'll get false primes much earlier, such as 1729 and 2465 when checking with 2 and 3.
I was wishing they'd point out why this test doesn't fall for Carmichael numbers, oh well
This is super cool and interesting, but I'm left to wonder why in the heck it works like it does.
This looks very similar to Fermat's Little Theorem, I can't remember whether Numberphile's ever done a video on the topic but some other channels definitely have (I'd recommend Mathologer's)
@@alexpotts6520 Numberphile does have a video on this topic called "Liar Numbers".
The most "dishonest" Witness is 1: 1^X=1 and 1modY=1 so it will always say "yup it's prime".
You know what does this video and the fed balance sheet have in common?
Billions are missing
The way the test is described in the video, it fails for Fermat primes like 257. When you subtract 1 and take out the 2s from what's left, the d value just becomes 1, so very few witnesses will yield a remainder of +-1 even though the test number is prime.
It also fails for primes lying above multiples of large powers of 2, such as 193, where d becomes 3. For instance, with a witness of 3, of course its cube (27) is not +-1 (mod 193), so the supplemental task starting at 8:08 is necessary rather than optional.
Something that wasn’t said in the video is that there’s a number that’s trivially always a strong liar if the number isn’t prime: 1, because 1 to the power of anything is 1, which is congruent to 1 modulo anything. 1 is the kind of witness who just wants to get out of the courtroom ASAP, so it’ll accuse anyone on the stand and leave.
12:45 The better the witness, the bigger the price tag.
When Matt talked about how large 23^373 was I was thinking: just punch it in Wolfram Alpha. Glad to see I was right.
...Or calculate it in python.
1,662,803 - the Dirty Harry of witnesses x)
I loved "primey". People assume that it's a strict primality test, but actually from a non-subjective viewpoint it's more like a big ball of wibbly-wobbly primey-wimey stuff.
I love what you did there!!
I didn't understand a word of this, but enjoyed it immensely.
1 is perfectly unreliable, given that 1^d = 1 mod n for all n
Watching this at 7:47pm😂
I am looking forward to Legal Eagle's interpretation of this case.
The fact that all these large numbers feel so random is what makes this so interesting tbh lol
Can you guys see whats so hard about Mersenne primes? I have this sneaky feeling twin primes and Mersenne primes are some strange bedfellows.
Well first of Mersenne numbers have their own primality test which only works for them and is much more efficient than this one. Also 2 is a liar for all Marsenne Numbers (and all Fermat Numbers), using this test with 2 will same Prime for all Marsenne Numbers, whether prime or composite
I love how they still have the same cup Grant Sanderson used for a challenge
The primes are the best witnesses because they know who's in their crime family
These witnesses have had a very interesting career. They randomly fly from being witnesses, to investigators to jurors. They really don't play by any one's rules.