Monthly Archive

You are currently browsing the monthly archive for March 2024.

The relationship between password strength, length, and alphabet

March 31, 2024 in General | Leave a comment

This is just a little exercise in partial differentiation

Introduction

So, you have a password of length $L$ from an alphabet $A$ . Suppose you have a choice to increase the length, $L\to L+1$ , vs the alphabet size $|A|\to |A|+1$ . Which will make your password more secure?

In this sense we will assume that passwords are subject only to random guesses, and so we make the simple assumption that given the data $(|A|,L)$ , the larger the number of possible passwords, the more secure the password.

The set of passwords is $\underbrace{A\times A\times \cdots \times A}_{L\text{ times}}$ . This has size $|A|^L$ .

Simple Numerics

A simple approach is to simply make a table:

An eyeballing of this will tell you that most of time it appears that increasing the length is preferable to increasing the alphabet size. But then again, alphabet size jumps tend to be larger, e.g. 26 to 52, 52 to 62, etc.

Suppose you have a length $L$ password from the alphabet $A=\{a,b,\dots,z\}$ . Are you better off going to length $L$ , or going to the alphabet of size $62$ , with the capital letters and the numebers? As it happens, it depends on $L$ . For $L<5$ , you should increase the length, but for $L\geq 6$ , you should double the size of the alphabet. This is typical.

Some analysis

Consider a password from a set of $|A|^L$ . Consider the two options, for constant $\alpha,\beta$ :

increase the alphabet size: $|A|\to \alpha|A|$ , or
increase the password length $L\to L+\beta$ .

If we look what these do to the number of passwords:

$|A|^L\to (\alpha|A|)^L\to \alpha^L|A|^L$ vs
$|A|^{L+\beta}\to |A|^\beta|A|^L$ ,

we are comparing $\alpha^L$ to $|A|^\beta$ , and $\alpha,\,\beta$ are constant, we are comparing the exponential function $x\mapsto \alpha^x$ and the polynomial function $x\mapsto x^\beta$ . While increasing the password length initially can do better, as $|A|$ and particularly $L$ increases, the exponential function speeds past the polynomial function, so eventually, it will make more sense to increase the alphabet size. Our eyeballing has let us down.

For example, from the table above, at $|A|=20$ and $L=14$ , it doesn’t appear to be even close, here at $\alpha=21/20$ , and $\beta=1$ , you get far more security increasing the length.

But for a fixed $|A|=20$ , there exists a length for which it makes more sense to increase the alphabet by a factor of $21/20$ . The answer is 61.

So, if you have a length 61 password from an alphabet of size 20, you are better off increasing the alphabet size.

I guess what is relevant here are the following questions: at $|A|=26,\,52,\,62,\,94$ (adding the special characters), what are the answers?

If $|A|=26$ , and $L<5$ , you could increase the length of the password rather than jumping to $|A|=52$ .
If $|A|=52$ , and $L<23$ , you could increase the length of the password rather than jumping to $|A|=62$ .
If $|A|=62$ , and $L<10$ , you could increase the length of the password rather than jumping to $|A|=94$ .

Going to special characters only makes sense in our framework if there is also a password length condition of 10 or more.

Partial Differentiation

This wasn’t even what I wanted to do here, which was to approximate this question using partial differentiation. In all these questions we are asking about what happens to $|A|^L$ when we change $|A|$ and keep $L$ constant and vice versa. So partial differentiation. I guess the problem is $|A|$ and $L$ are discrete, rather than continuous, but sure $x^L$ and $|A|^x$ are perfectly good functions to differentiate. Let $N:=|A|^L$ .

Even I can differentiate with respect to $|A|$ (in fact, on first go I wrote with respect to $L$ here, and got it wrong!):

$\displaystyle \dfrac{\partial N}{\partial |A|}=L\cdot |A|^{L-1}$ .

We might use some logs to differentiate with respect to $L$ :

$\ln(N)=\ln(|A|^L)$

$\ln(N)=L\cdot \ln(|A|)$

$\displaystyle \implies \dfrac{1}{N}\dfrac{\partial N}{\partial L}=\ln(|A|)$

$\displaystyle \implies \dfrac{\partial N}{\partial |A|}=N\ln(|A|)=\ln |A|\cdot |A|^L$ .

These partial derivatives estimate that if $|A|\to \alpha|A|$ (a change of $(\alpha-1)|A|$ and $L\to L+\beta$ ,

$\Delta N\approx \dfrac{\partial N}{\partial |A|}\Delta |A|=L|A|^{L-1}(\alpha-1)|A|=(\alpha-1)L|A|^L=(\alpha-1)LN$

$\Delta N\approx \dfrac{\partial N}{\partial L}\Delta L=\ln |A|\cdot |A|^L\beta=\beta \ln(|A|)N$ ,

so, approximately, we are left comparing $\beta \ln(|A|)$ and $(\alpha-1)\cdot L$ . And here we see $\ln(|A|)$ vs $L$ … eventually $L\gg \ln(|A|)$ if both grow, giving us the same answer as before.

On the number of fixed points of conditioned quantum permutations

March 31, 2024 in Probability Theory, Quantum Groups, Research | Leave a comment

Consider the symmetric group $S_N$ . Let $\mathrm{fix}_N \in C(S_N)$ count the number of fixed points of a permutation $\sigma\in S_N$ . Where $X\sim \mathrm{Poi}[1]$ , we have that for a random permutation $\xi_N\in S_N$ chosen with respect to the uniform distribution, the $\mathrm{fix}_N$ converges in distribution to $X$ in the sense that:

$\displaystyle \lim_{N\to \infty}\mathbb{P}[\mathrm{fix}_N(\xi_N)=m]=\mathbb{P}[X=m]$ .

In this note we will look at the distribution in the case where the uniform distribution is conditioned on $\xi_N(1)=1$ .

Theorem

Let $\xi_N\in S_N$ be chosen according to the distribution uniform on permutations for which one is a fixed point. The number of fixed points has distribution $1+\mathrm{Poi}[1]$ in the sense that, where $X\sim \mathrm{Poi}[1]$ ,

$\displaystyle \lim_{N\to \infty}\mathbb{P}[\mathrm{fix}_N(\xi_N)=m]=\mathbb{P}[X=m-1]$ .

Proof: What can be shown, ostensibly from stuff from the quantum permutation side of the house is that, where $h_N$ is integration against the uniform distribution, and $\widetilde{h_N}$ is integration against the uniform distribution on permutations with one a fixed point, that, for $k<N$ :

$\displaystyle \widetilde{h_N}(\mathrm{fix}_N^k)=h_N(\mathrm{fix}_N^{k+1})=B_{k+1}$ ,

the $(k+1)$ -st Bell number. Now consider the moments of $1+X$ :

$\displaystyle \sum_{t=0}^\infty t^k\mathbb{P}[1+X=t]=\sum_{t=0}^\infty t^k\mathbb{P}[X=t-1]$

$\displaystyle =\sum_{t=1}^\infty t^k\frac{e^{-1}}{(t-1)!}$

$\displaystyle \underset{s=t-1}{=}\sum_{s=0}^\infty(s+1)^k\frac{e^{-1}}{s!}$

$\displaystyle =\sum_{s=0}^\infty\sum_{i=0}^k\binom{k}{i}s^i \frac{e^{-1}}{s!}$

$\displaystyle =\sum_{i=0}^k\binom{k}{i}\sum_{s=0}^\infty s^i\frac{e^{-1}}{s!}$

$\displaystyle =\sum_{i=0}^k \binom{k}{i} B_k=B_{k+1}$ ,

using the fact that the Bell numbers are the moments of that Poisson distribution and the standard recurrence for the Bell numbers.

Local vs Global Conditioning of Quantum Permutations

In the quantum case we define

$\displaystyle \mathrm{fix}_N:=\mathrm{Tr}(u)$ ,

where $u\in M_N(C(S_N^+))$ is the fundamental magic representation. The moments of $\mathrm{fix}_N$ with respect to the Haar state are the Catalan numbers and it follows that the law of $\mathrm{fix}_N$ is a Marchenko-Pastur distribution, with density

$\displaystyle \dfrac{1}{2\pi}\sqrt{\frac{4}{t}-1}$ :

Note that when we measure the Haar state with some finite spectrum version of $\mathrm{fix}_N$ we find:

the probability of finding an integer number of fixed points is zero, and
independently of $N$ , the probability of finding more than four fixed points is zero.

In the classical case above when we chose the permutation uniformly from those who fix one, there are two ways of viewing it:

we pick an element of $S_N$ that fixes one, OR
we consider the isotropy subgroup $S_{N-1}\subset S_N$ and choose our permutation from $S_{N-1}$ .

Classically, these are the same thing. In the quantum case these two things can be interpreted differently. The second case is quite clear in the quantum case. For $N>4$ , we take the isotropy $S_{N-1}^+\subset S_N^+$ via the quotient $C(S_N^+)\to C(S_N^+)/\langle1-u_{11}\rangle$ .

The analogue of the uniform distribution on $S_{N-1}\subset S_N$ here is the Haar idempotent $h_{C(S_{N-1}^+)}\circ \pi$ . Note this maps $\mathrm{fix}_N$ to $1+\mathrm{fix}_{N-1}$ . Now, using the fact that $h_{C(S_{N-1}^+)}(\mathrm{fix}_{N-1})=C_k$ , the Catalan number, we have that the moments of $\mathrm{fix}_N$ with respect to $h_{C(S_{N-1}^+)}\circ \pi$ is the binomial transform of the Catalan numbers (the binomial transform of $B_1,\dots,B_k$ is $B_{k+1}$ ). It follows, using similar stuff to the above, that the distribution of $\mathrm{fix}_N$ with respect to $h_{C(S_{N-1}^+)}\circ \pi$ is just a shifted version of Marchenko–Pastur:

I guess this is marginally more interesting than the unshifted version.

Now, what about an analogue of “we pick an element of $S_N$ that fixes one”. So if we take the Haar state and measure the observable $u_{11}\in C(S_N^+)$ that asks of a quantum permutation, does it fix one, we get, conditioned on this, the state:

$\displaystyle h_1(f):=N\cdot h(u_{11}fh_{11})=\dfrac{h(u_{11}fu_{11})}{h(u_{11})}\qquad (f\in C(S_N^+))$ .

And, it turns out, as above, using stuff from the quantum permutation side of the house:

$\displaystyle h_1(\mathrm{fix}_N^k)=h(\mathrm{fix}_N^{k+1})=C_{k+1}$ .

Quite quickly from here we find that the density of the distribution of $\mathrm{fix}_N$ with respect to $h_1$ is

$\displaystyle \frac{t}{2\pi}\sqrt{\frac{4}{t}-1}$

This is so interesting:

it doesn’t change the support — we still find between 0 and 4 fixed points,
we have a new symmetry about $\mathrm{fix}_N=2$ , we had another unexpected symmetry here.
the mean jumps from one to two, that is not unexpected, but
the mode jumps from zero to two!
even though we have observed one to one, there can still be less than one fixed point when we measure… and this happens with probability $\approx 1/5$ .

The next obvious question is what happens with:

$\displaystyle f\mapsto \dfrac{h_1(u_{22}fu_{22})}{h_1(u_{22})}\qquad (f\in C(S_N^+))$

Epilogue?

So what about this local vs global conditioning? Well, no matter what subsequent measurements are made to $h_{C(S_{N-1}^+)}\circ \pi$ , we will always find that one is a fixed point. That conditioning is ‘global’.

This is not the case with $h_1$ , and why the support of the law is not bounded above one, like that of the globally conditioned $h_{C(S_{N-1}^+)}\circ \pi$ . In fact, there is a non-zero probability that $h_1$ is observed to fix two but then subsequently not fix one anymore. That conditioning was only local: the probability that $h_1$ fixes one is 100%… but subsequent measurements can destroy that conditioning… it is only local.

MATH7016: Spring 2024, Week 9

March 21, 2024 in MATH7016 | Leave a comment

Remaining Assessment

Expect updates early next week giving information about the final two assessments.

Oh, and there is one more round to go in the MCQ with cash prizes available.

Written Assessment Solutions

See here:

writtenassessment12024solutions Download

Week 9

We finished our work on Laplace’s Equation and then started – and finished looking at the Heat Equation.

Students who missed the lecture on Wednesday can catch up with the Lecture videos on Canvas.

We looked at Lab 7, based on Laplace’s Equation

Here on is provisional on when I go on paternity leave

Week 10

We will have tutorial time towards the 40% Written Assessment on Tuesday and Wednesday.

For Lab 8, the theory is examinable in the final written assessment but the VBA not examinable outside of Autumn repeat exam.

If I go on paternity leave a number of videos will have been produced:

an intro to Lab 8,
and outro to Lab 8,
four hours and 10 minutes of worked examples

You will be instructed to replace your four hours of lab and lecture time with engagement with these materials.

Week 11

I will almost certainly be on paternity leave. Your VBA 2 assessment will take place and it will be invigilated. NOTE DME2D will have their assessment at A285 and NOT B151 (at the usual time slot)

You will be instructed to replace your two hours of lecture time with engagement with the four hours and 10 minutes of worked examples.

Week 12

I will probably be on paternity leave. Your Written Assessment 2 will take place in the Melbourne.

You will be instructed to replace your Tuesday lecture time with engagement with the four hours and 10 minutes of worked examples.

If I am back from paternity leave your Tuesday lecture will be a tutorial.

Study

Study should consist of

doing exercises from the notes
completing VBA exercises

Student Resources

Please see the Student Resources tab on the top of this page for information on the Academic Learning Centre, etc..

MATH7021: Spring 2024, Week 9

March 21, 2024 in MATH7021 | Leave a comment

Students who did not take advantage of the ample tutorial time this week (and those who did) are free to email me questions over Easter. Please send screenshots of your attempts.

15% Assignment 2

Assignment 2 is in the manual. It could be started now.

Week 9

We had a bumper week of Chapter 3 tutorials.

Week 10

I will probably not be on paternity leave yet, in which case we will have a final Chapter 3 tutorial on Tuesday before doing systems of differential equations on Wednesday and Thursday, with some tutorial time possible on Thursday.

If I do go on paternity leave, a colleague of mine is due to take ye. If it happens that this cover is late, only coming on Thursday, I will have pre-recorded lectures on systems of differential equations which you should watch instead of the lectures on Tuesday and Wednesday. Then my colleague will do a Chapter 3/ systems of differential equations tutorial with you on Thursday.

Week 11

I will be on paternity leave.

Tuesday will be a tutorial on systems of differential equations and then ye will work on double integration and when we finish that section we will have tutorials.

Week 12

I might be back from paternity leave.

Tuesday will be a tutorial on double integration and then ye will work on triple integration. When finished ye will have tutorial time on that topic.

Week 13, Review Week

We will have tutorial time.

Study

Please feel free to ask me questions about the exercises via email or on this webpage.

Student Resources

Please see the Student Resources tab on the top of this page for information on the Academic Learning Centre, etc..

MATH7021: Spring 2024, Week 8

March 14, 2024 in MATH7021 | Leave a comment

Again, things are more serious now as we start Chapter 3. We must work hard on this material:

because without doing so you could be very, very lost on 15% Assignment 2 (and 35% exam question), and
because if you are going into Level 8 Structural Engineering it will be assumed that you are competent with the Chapter 3 material

Students who missed today, Thursday 14 March should really watch the videos covering Section 3.4 before Tuesday.

Week 8

The week will be focused on finishing the part of Chapter 3 examinable in Assignment. We did this, by looking at partial fractions, the inverse Laplace transform, and the application of the Laplace Transform to differential equations. We managed some tutorial time on Wednesday but the double was all lecture.

15% Assignment 2

Assignment 2 is in the manual, has a hand-in date of 12 April, and once you have had some tutorial time, you can start this.

Week 9

This will be a bumper week of Chapter 3 tutorials.

Week 10

Week 11

I will be on paternity leave.

Tuesday will be a tutorial on systems of differential equations and then ye will work on double integration and when we finish that section we will have tutorials.

Week 12

I might be back from paternity leave.

Tuesday will be a tutorial on double integration and then ye will work on triple integration. When finished ye will have tutorial time on that topic.

Week 13, Review Week

We will have tutorial time.

Study

Please feel free to ask me questions about the exercises via email or on this webpage.

Student Resources

Please see the Student Resources tab on the top of this page for information on the Academic Learning Centre, etc..

MATH7016: Spring 2024, Week 8

March 14, 2024 in MATH7016 | Leave a comment

Assessment Corrections

The VBA results have been released and all groups will have one chance to get some quick feedback on what they submitted. If this doesn’t or hasn’t worked for you, please feel free to send an email.

I have set a target of Week 9 for your Written Assessment results.

Week 8

We continued with Chapter 2, describing the implementation of the Gauss-Seidel method. We have stopped (geddit) short of giving the stopping rule, ye will see this on Tuesday.

We did Lab 6 on boundary value problems, and it is relevant for VBA Assessment 2 in Week 11.

Week 9

We will finish our work on Laplace’s Equation and then start looking at the Heat Equation.

We will look at Lab 7, based on Laplace’s Equation

Because every lab counts, the Bank Holiday labs of DME2A are going to be rescheduled to Tuesday: on Tuesday March 19 we will have the following:

DME2A, 14:40-16:20, DME2E 16:20-18:00, A285

Here on is provisional on when I go on paternity leave

Week 10

We will finish our work on the Heat Equation and have tutorial time on Wednesday.

For Lab 8, the theory is examinable in the final written assessment but the VBA not examinable outside of Autumn repeat exam.

If I go on paternity leave a number of videos will have been produced:

a video covering the last lecture of new material,
an intro to Lab 8,
and outro to Lab 8
two hours and 40 minutes of worked examples

You will be instructed to replace your four hours of lab and lecture time with engagement with these materials.

Week 11

I will almost certainly be on paternity leave. Your VBA 2 assessment will take place and it will be invigilated.

You will be instructed to replace your two hours of lecture time with engagement with the two hours and 40 minutes of worked examples.

Week 12

I will probably be on paternity leave. Your Written Assessment 2 will take place in the Melbourne.

You will be instructed to replace your Tuesday lecture time with engagement with the two hours and 40 minutes of worked examples.

If I am back from paternity leave your Tuesday lecture will be a tutorial.

Assessment

See Canvas for the assessment schedule.

Study

Study should consist of

doing exercises from the notes
completing VBA exercises

Student Resources

Please see the Student Resources tab on the top of this page for information on the Academic Learning Centre, etc..

MATH7021: Spring 2024, Week 7

March 7, 2024 in MATH7021 | Leave a comment

Again, things are more serious now as we start Chapter 3. We must work hard on this material:

because without doing so you could be very, very lost on 15% Assignment 2 (and 35% exam question), and
because if you are going into Level 8 Structural Engineering it will be assumed that you are competent with the Chapter 3 material

Timetable Change

The Monday class is now moved to A243L at 13:00 on Tuesdays. This allows us to spread out tutorial time better, and hopefully is logistically better for you.

Week 7

On Monday, we had a final Chapter 2 tutorial.

Then the rest of the class will be given over to partial fractions and then the inverse Laplace transform.

On Wednesday and Thursday we had some tutorial time on partial fractions and the cover up method.

Week 8

The week will be focused on finishing Chapter 3.

15% Assignment 2

Assignment 2 does not yet have a hand-in date (watch this space). Assignment 2 is in the manual, and once you finish the exercises in the manual you will be in a great position to start.

Week 9

This should be a bumper week of Chapter 3 tutorials if we have finished Chapter 3.

The below is very much provisional

Week 10

We will do systems of differential equations.

Week 11

We will work on double integration and when we finish that section we will have tutorials.

Week 12

We will work on triple integration. When finished we will have tutorial time on that topic.

Week 13, Review Week

We will go through an exam paper, answer questions, and have tutorial time as appropriate.

Study

Please feel free to ask me questions about the exercises via email or on this webpage.

Student Resources

Please see the Student Resources tab on the top of this page for information on the Academic Learning Centre, etc..

MATH7016: Spring 2024, Week 7

March 7, 2024 in MATH7016 | Leave a comment

Room Change this Week

MF1 is unavailable on Wednesday afternoon, the 13^th of March. Check communication from your 14:00 and 15:00 lecturers. We are in B282 at 4 pm.

Week 7

We finished looking at boundary value problems and then started Chapter 2, Partial Differential Equations.

We had Written Assessment 1.

In VBA we finished what we are doing on Lab 4 and then looked at Lab 5. Lab 5 is not examinable as VBA but the theory of it, the theory of RK, that is examinable in Written Assessments 1 and 2. Some students instead used the time to prepare for Written Assessment 1.

Assessment Corrections

Let us set a target of Week 8 for your VBA results and Week 9 for your Written Assessment results.

Week 8

We will continue with Chapter 2.

Lab 6 is on boundary value problems and relevant for VBA Assessment 2 in Week 11.

Week 9

Section 2.1

Lab 7

Because every lab counts, the Bank Holiday labs of DME2A are going to be rescheduled to Tuesday: on Tuesday March 19 we will have the following:

DME2A, 14:40-16:20, DME2E 16:20-18:00, A285

Here on is provisional:

Week 10

Section 2.2

Lab 8 (theory examinable in final written assessment but VBA not examinable outside of Autumn repeat exam)

Week 11

Finish Section 2.2 and then tutorial time

Assessment

See Canvas for the assessment schedule.

Study

Study should consist of

doing exercises from the notes
completing VBA exercises

Student Resources

Please see the Student Resources tab on the top of this page for information on the Academic Learning Centre, etc..

	J.P. McCarthy on MATH6040: Spring 2022, Week…
	J.P. McCarthy on MATH6040: Spring 2022, Week…
	J.P. McCarthy on MATH7019: Winter 2020, Week…
	J.P. McCarthy on MATH7019: Winter 2020, Week…
	A Sufficient Conditi… on Almost All Trees have Quantum…

Monthly Archive

Introduction

Simple Numerics

Some analysis

Partial Differentiation

Share this:

Theorem

Local vs Global Conditioning of Quantum Permutations

Epilogue?

Share this:

Remaining Assessment

Written Assessment Solutions

Week 9

Week 10

Week 11

Week 12

Study

Student Resources

Share this:

15% Assignment 2

Week 9

Week 10

Week 11

Week 12

Week 13, Review Week

Study

Student Resources

Share this:

Week 8

15% Assignment 2

Week 9

Week 10

Week 11

Week 12

Week 13, Review Week

Study

Student Resources

Share this:

Assessment Corrections

Week 8

Week 9

Week 10

Week 11

Week 12

Assessment

Study

Student Resources

Share this:

Timetable Change

Week 7

Week 8

15% Assignment 2

Week 9

Week 10

Week 11

Week 12

Week 13, Review Week

Study

Student Resources

Share this:

Room Change this Week

Week 7

Assessment Corrections

Week 8

Week 9

Week 10

Week 11

Assessment

Study

Student Resources

Share this:

Recent Comments

Categories