Strong Password Detection in Python

This is a problem from “Automate the boring stuff”.

Write a function that uses regular expressions to make sure the password string it is passed is strong. A strong password is defined as one that is at least eight characters long, contains both uppercase and lowercase charac- ters, and has at least one digit. You may need to test the string against mul- tiple regex patterns to validate its strength.

How to improve this code?

#! /usr/bin/python3  import re  def uppercase_check(password):     if re.search('[A-Z]', password): #atleast one uppercase character         return True     return False  def lowercase_check(password):     if re.search('[a-z]', password): #atleast one lowercase character         return True     return False  def digit_check(password):     if re.search('[0-9]', password): #atleast one digit         return True     return False   def user_input_password_check():     password = input("Enter password : ")         #atleast 8 character long     if len(password) >= 8 and uppercase_check(password) and lowercase_check(password) and digit_check(password):         print("Strong Password")     else:         print("Weak Password")  user_input_password_check() 

Do non-administrator Windows accounts need strong passwords?

I have always used long passphrases for my own Windows user accounts. But I know some people who use moderately common passwords (we’ll say they’re in the top 1,000 most used passwords, but not in the top 100).

From Why do we lock our computers?, I see that locking protects you from attackers who are unskilled or not prepared, and can even slow down prepared attackers for a few minutes. But if a capable attacker is alone with your computer for any extended period of time, they can get in if you don’t have full-disk encryption.

Does it make sense to use a strong account password (that is, something not in any password list)? Nobody is going to try the top 1,000 passwords if they’re alone with your computer for a few minutes, and if they’re with your computer for longer than that they can use other means.

Suppose RDP is disabled on the computer and the administrator account has a lengthy, unique passphrase. We’ll also suppose that the user’s password is not one they use elsewhere. Is there any attack that becomes easier if a non-administrator user password is in a list of common passwords?

Strong chromatic index of some cubic graphs


Definition (somewhat informal) A strong edge $ k$ coloring of a cubic (3-regular) graph is a proper $ k$ coloring of its edges so that any edge together the four edges adjacent to it are colored with 5 colors. The strong chromatic index $ \chi_S(G)$ of a cubic graph $ G$ is the smallest number $ k$ such that $ G$ has a strong edge $ k$ coloring.

Andersen, in [1], showed that if $ G$ is a sub-cubic graph (a graph of max degree 3), then $ \chi_S(G)\le 10$ . In the same paper, he proposed the following:

Conjecture [Andersen, 1992] There is a constant $ g$ such that if a cubic graph $ G$ is such that girth $ \gamma(G)\ge g$ , then $ \chi_S(G)=5$ .

This conjecture is highly significant, as the truth of it would imply the truth of several notorious graph theoretical conjectures for all (cubic) graphs of large enough girth.

As a bit of background information to our question ahead, some (as yet very incomplete) computer investigations would seem to indicate that if $ G$ is bridgeless (and of girth at least 4, although we are not sure this is really needed), then $ \chi_S(G)\le 8$ , and also, if $ \gamma(G)\ge 5$ then $ \chi_S(G)\le 7$ , and if $ \gamma(G)\ge 9$ then $ \chi_S(G)\le 6$ . Finally, we have verified that the (3,17)-cage listed in [2] does not have a strong edge 5 coloring, and that the (3,18)-cage in [2] has a strong edge 5 coloring. We are currently trying to establish the strong chromatic index of several graphs of girth larger than 9 listed in [2], and we are also trying to establish whether the (3,19)-cage in [2] has a strong edge 5 coloring. And we should probably look at a lot more graphs with small girth. We will update this post as this information is further verified, or refuted – our computations are geared at the moment towards graphs with girth higher than 4. We need to do a lot more checking on graphs with girth 3 and 4 and we acknowledge that this is lacking. There is only so much compute time available … however, we believe there is a firm basis for our main question (question 1) ahead.

Before we pose our question, we need a definition.

Definition Let an $ n$ -prismatic graph be a cubic graph obtained by joining two disjoint circuits of order $ n$ with a perfect matching.

Our first question is then:

Question 1 [main question] Let $ G$ be prismatic. Then the strong chromatic index of $ G$ is at most 8. Moreover, if the girth of $ G$ is greater than 4, then the strong chromatic index of $ G$ is at most 7. As always in our posts, prove of provide a counterexample.

The nature of a possible proof of this is almost necessarily algorithmic. An inductive proof of the more general statement that bridgeless graphs of girth at least 4 have strong chromatic index at most 8 seems a bit out of reach at the moment. Indeed, in working with general graphs of girth 4 and finding subgraphs which are strong 8-critical, we have found over a thousand that are not isomorphic, and fairly large. Of course, there are a few that are small and that occur a lot more often.

In [1] a linear time algorithm to find a strong coloring with at most 10 colors is given. We would also like to know if:

Question 2 Is there a fast (linear time?) and simple algorithm to find a strong edge 8 coloring of a bridgeless cubic graph?

[1] Andersen, L. D., The strong chromatic index of a cubic graph is at most 10, Discrete Mathematics, 108 (1992) 231-252

[2] Royle, G. Cubic Cages, staffhome.ecm.uwa.edu.au/~00013890/remote/cages/index.html#data

Strong chromatic index of cubic gaphs of very high girth


Definition (informal) Let $ G$ be a cubic graph (no other conditions are placed). A strong edge coloring of $ G$ is a proper coloring of the edges with at least 5 colors such that for every edge $ e\in E(G)$ , five different colors are used to color $ e$ and its four adjacent edges. The strong chromatic index $ \chi_S(G)$ of $ G$ is the smallest number of colors required to get a strong edge coloring of $ G$ .

There are a number of open conjectures related to the strong chromatic index of cubic graphs. One such conjecture is the following:

Conjecture [Andersen?,1992,[1]] There is a constant $ k$ , such that for graphs of girth $ \gamma(G)\ge k$ one has $ \chi_S(G)=5$ .

We would like to investigate this conjecture. The truth of it has many implications for graphs in general.

One can see from computer experiments (not exhaustive) that already for $ \gamma(G)\ge 5$ one would seem to have $ \chi_S(G)\le 7$ . For $ \gamma(G)\ge 9$ it would appear that $ \chi_S(G)\le 6$ , although surely this requires further testing. We wonder how high the girth must be to bring down the strong chromatic index to 5. We do not have graphs of girth higher than 9 available for computer experiments. So our question is the following (note we have no notion of what cubic graph generation is like):

Question Is there a (public?) implementation of a cubic graph generating function where the girth can be made arbitrarily high? Ideally, such a function generates graphs that are not isomorphic, in some sequence, for a specified (and possible) number of vertices, and it can be started and stopped at will. The idea is to generate several examples (in the hundreds), perhaps exhaustively for relatively few vertices, in order to carry out some computer experiments that would allow us to “guess” the right value for the girth required to get a strong chromatic index equal to 5. Ideally, the graphs produced are in graph6 format. Ideally also, the function, if publicly available, is compiled and can be run from Mathematica (in general, this is possible).

Alternatively, is there a list of cubic graphs with very high girths (higher than 9, probably significantly so)?

I am relatively new to this site; if this question (request) is inappropriate for MO, leave a comment and explanation, and it will be deleted.

[1] Andersen, L. D., The strong chromatic index of a cubic graph is at most 10, Discrete Mathematics 108 (1992) 231-252

[2] Horák, P, Qing, H., Trotter, W., Induced matchings in cubic graphs, Journal of Graph Theory 17 2 (1993) 151-160

Strong uniqueness of Euler’s totient function

Let $ f:\mathbb N\to \mathbb C$ be some arithmetical function. Define $ \varphi_f(n)$ by the following formula:

$ $ \varphi_f(n)=\sum_{\substack{k\leq n \ (k,n)=1}}f(k). $ $

In other words, $ \varphi_f(n)$ is the sum of $ f$ over totatives of $ n$ . For example, if $ f=\delta_1(n)$ then $ \varphi_f(n)=1$ , if $ f=1$ then $ \varphi_f(n)=\varphi(n) -$ Euler’s totient function. Assume that $ f$ is completely multiplicative. Examination of the first few values of $ f$ (up to $ \approx 40$ ) shows that if $ \varphi_f$ is multiplicative only if $ f=1$ or $ f=\delta_1$ .

Obviously, direct analysis of 40 or so cases is not the most illuminating way to prove this type of proposition. This leads us to a bit more general question. Let us call an arithmetical function $ g$ eventually multiplicative if there is a multiplicative function $ G$ such that $ g(n)=G(n)$ for $ n$ large enough. Is it true that if $ f$ is completely multiplicative and $ \varphi_f$ is eventually multiplicative then either $ f=\delta_1$ or $ f=1$ ?

Helly vs Strong Helly property of Hypergraphs

I am not clear about the difference between Helly and Strong Helly property. For example hypergraph H(V, E), V = { 1,2,3 } and E = {(1,2), (2,3), (1,3)} has non-empty set for each pair of intersection, which makes it qualify as Helly (but not strong Helly) however, this triangle hypergraph is not considered as Helly hypergraph. Any insight and correction would be appreciated.

A simple case of a strong version of the Berge-Fulkerson conjecture

Let $ G$ be a bridgeless cubic graph. Define a Fulkerson cover of $ G$ to be a collection of six perfect matchings in $ G$ , not necessarily distinct, which together cover each edge of $ G$ twice. We say that $ G$ admits a Fulkerson cover if there is a Fulkerson cover for $ G$ .

Fulkerson, and also Berge, proposed the following notorious conjecture.

Conjecture [Fulkerson, 1971, and Berge]. Every bridgeless cubic graph admits a Fulkerson cover.

A natural question that comes to mind is whether for any bridgeless cubic graph $ G$ and any perfect matching $ M$ of $ G$ there is a Fulkerson cover of $ G$ which contains $ M$ . We call a pair $ (G,M)$ a configuration and if $ G$ admits a Fulkerson cover that includes $ M$ we say that $ (G,M)$ extends to a Fulkerson cover. It is possible to see that in general (see figure for an example of a graph and a perfect matching which does not extend to a Fulkerson cover), this is not true:

(G,M) does not extend to a Fulkerson cover

However, we are guessing that if $ G$ is cyclically edge-5-connected, then this is true (we hesitate to call it a conjecture at this stage because we do not have enough evidence data):

Guess If $ G$ is cyclically edge-5-connected cubic graph and $ M$ is any perfect matching of $ G$ then $ G$ admits a Fulkerson cover which includes $ M$ .

For a definition of cyclical edge connectedness see the reference below 1. This looks very hard to prove, in fact, it would imply Berge and Fulkerson’s conjecture. But our question pertains to a special case of this conjecture, where the cyclical connectedness restriction is lifted.

Let a prism be a cubic graph $ G$ consisting of two disjoint circuits of the same length connected by a perfect matching $ M$ . We say that the configuration $ (G,M)$ is prismatic. Our question is the following.

Question Let $ (G,M)$ be a prismatic configuration. Does it extend to a Fulkerson cover?

One can think of this problem as an edge coloring problem. To do this, double all the edges not in $ M$ . Then the resulting graph is a 5-regular multigraph. The question then becomes whether the chromatic index of this multigraph is 5.

1 Nedela, R. and Skoviera, M. Atoms of cyclic connectivity in cubic graphs, Mathematica Slovaca 45 5 (1995) 481-499.

Telling users passwords don’t match and aren’t strong enough

I have two functions in my user registration form

  • One checks the password and confirmed password are the same.
  • The other checks if the password is strong enough.

I have two presentation related questions

  • What words should I use if the passwords don’t match or isn’t strong enough? I have a text field beside the first password which is initially empty but gets updated as each character is typed in (I can add a second text field beside the confirm password part).
  • When and in what order should the functions be called? For example if I only call the passwords match function on the confirm password section then if the user goes back and changes the first password things will get messed up. If I call the passwords match function at the first time the user types in the password then it will override the message about the password not being strong enough or the strong enough password will override the “password don’t match” message.

The function that checks if the password is strong enough is real simple, just to prevent “123” and password. In the future I’d like to make an option to unmask the password and only have one field and no confirm.