11 - Revision history

Vipul: /* Prime-generating polynomials */

2012-01-15T21:48:44Z

Prime-generating polynomials

← Older revision		Revision as of 21:48, 15 January 2012
Line 77:		Line 77:
	==Prime-generating polynomials==		==Prime-generating polynomials==

	Below are some polynomials that give prime numbers for small input values, which give the value 17 for suitable input choice.		Below are some polynomials that give prime numbers for small input values, which give the value 11 for suitable input choice.

	{\| class="sortable" border="1"		{\| class="sortable" border="1"

Vipul: /* Multiples */

2012-01-15T21:47:09Z

Multiples

← Older revision		Revision as of 21:47, 15 January 2012
Line 74:		Line 74:

	Note that in this case, all the quadratic nonresidues other than 10 (which is -1 mod 11) are primitive roots. This follows from the fact that [[quadratic nonresidue that is not minus one is primitive root for safe prime]].		Note that in this case, all the quadratic nonresidues other than 10 (which is -1 mod 11) are primitive roots. This follows from the fact that [[quadratic nonresidue that is not minus one is primitive root for safe prime]].

			==Prime-generating polynomials==

			Below are some polynomials that give prime numbers for small input values, which give the value 17 for suitable input choice.

			{\| class="sortable" border="1"
			! Polynomial !! Degree !! Some values for which it generates primes !! Input value <math>n</math> at which it generates 11
			\|-
			\| <math>n^2 - n + 5</math> \|\| 2 \|\| all numbers 1,2,3,4, because 5 is one of the [[lucky numbers of Euler]]. \|\| 3
			\|-
			\| <math>n^2 - n + 11</math> \|\| 2 \|\| all numbers 1-10, because 11 is one of the [[lucky numbers of Euler]]. \|\| 1
			\|}

	==Multiples==		==Multiples==

Vipul: /* Properties and families */

2012-01-15T21:46:04Z

Properties and families

← Older revision		Revision as of 21:46, 15 January 2012
Line 19:		Line 19:
	\|-		\|-
	\| [[satisfies property::regular prime]] \|\| fourth regular prime \|\| {{#lst:regular prime\|list}} \|\|		\| [[satisfies property::regular prime]] \|\| fourth regular prime \|\| {{#lst:regular prime\|list}} \|\|
			\|-
			\| [[satisfies property::lucky number of Euler]] \|\| fourth of six such numbers \|\| {{#lst:lucky number of Euler\|list}} \|\| <math>p</math> is of this kind iff <math>\mathbb{Q}(\sqrt{1 - 4p})</math> has class number 1, i.e., its ring of integers is a unique factorization domain.
	\|}		\|}

Vipul: /* Quadratic residues and nonresidues */

2012-01-03T20:43:19Z

Quadratic residues and nonresidues

← Older revision		Revision as of 20:43, 3 January 2012
Line 72:		Line 72:

	Note that in this case, all the quadratic nonresidues other than 10 (which is -1 mod 11) are primitive roots. This follows from the fact that [[quadratic nonresidue that is not minus one is primitive root for safe prime]].		Note that in this case, all the quadratic nonresidues other than 10 (which is -1 mod 11) are primitive roots. This follows from the fact that [[quadratic nonresidue that is not minus one is primitive root for safe prime]].

			==Multiples==

			===Interesting multiples===

			{\| class="sortable" border="1"
			! Number !! Prime factorization !! What's interesting about it
			\|-
			\| [[341]] \|\| [[11]] times [[31]] \|\| smallest [[Poulet number]] (also called Sarrus number), i.e., smallest [[Fermat pseudoprime]] to base 2
			\|-
			\| [[561]] \|\| [[3]] times [[11]] times [[17]] \|\| smallest [[Carmichael number]], i.e., smallest absolute pseudoprime
			\|}

Vipul: /* Discrete logarithm */

2012-01-02T22:47:51Z

Discrete logarithm

← Older revision		Revision as of 22:47, 2 January 2012
Line 52:		Line 52:
	\| 10 \|\| -1 \|\| 5 \|\| No \|\| [[quadratic nonresidue]]		\| 10 \|\| -1 \|\| 5 \|\| No \|\| [[quadratic nonresidue]]
	\|}		\|}

			Instead of 2, we could have taken 6, 7, or 8 as the base for discrete logarithm. The discrete logarithm thus obtained would differ from the original discrete logarithm via a multiplication by some suitable integer mod 10 (see [[base change for discrete logarithm]]).

	===Primitive roots===		===Primitive roots===

Vipul: /* Structure of integers mod 11 */

2012-01-02T22:46:34Z

Structure of integers mod 11

← Older revision		Revision as of 22:46, 2 January 2012
Line 52:		Line 52:
	\| 10 \|\| -1 \|\| 5 \|\| No \|\| [[quadratic nonresidue]]		\| 10 \|\| -1 \|\| 5 \|\| No \|\| [[quadratic nonresidue]]
	\|}		\|}

			===Primitive roots===

			The ''number'' of primitive roots equals the number of generators of the additive group of integers mod 10, which is the [[Euler totient function]] of 10, which is 4. Given any primitive root <math>a</math>, the primitive roots are those whose discrete log to base <math>a</math> is relatively prime to 10, In other words, they are the numbers <math>a,a^3,a^7,a^9</math>. The explicit list of primitive roots is 2,6,7,8.

			We note the following:

			* The fact that 2 is a primitive root can be deduced from the fact that [[safe prime has plus or minus two as a primitive root]], along with the fact that [[11]] is a [[safe prime]] that is congruent to 3 mod 8.

			===Quadratic residues and nonresidues===

			Of the ten congruence classes of invertible elements mod 11, five give quadratic residues and five give quadratic nonresidues. In terms of discrete logarithms, the quadratic residues correspond to even values and the quadratic nonresidues correspond to odd values of the logarithm. Explicitly, if <math>a</math> is a primitive root, the quadratic residues are <math>1,a^2,a^4,a^6,a^8</math> and the nonresidues are <math>a,a^3,a^5,a^7,a^9</math>.

			Alternatively, the quadratic residues can be computed by taking the squares of the first five natural numbers and reducing them mod 11.

			Explicitly, the quadratic residues are 1,3,4,5,9 and the quadratic nonresidues are 2,6,7,8,10.

			Note that in this case, all the quadratic nonresidues other than 10 (which is -1 mod 11) are primitive roots. This follows from the fact that [[quadratic nonresidue that is not minus one is primitive root for safe prime]].

Vipul: /* Discrete logarithm */

2012-01-02T22:39:35Z

Discrete logarithm

← Older revision		Revision as of 22:39, 2 January 2012
Line 27:		Line 27:
	{{discrete log facts to check against}}		{{discrete log facts to check against}}

	2 is a [[primitive root]] mod 11, so we can take it as the base of the discrete logarithm. We thus get an explicit bijection from the additive group of integers mod 10 to the multiplicative group of nonzero congruence classes mod 11, given by <math>m \mapsto 2^m</math>. The inverse of that mapping is the discrete logarithm, i.e., the discrete logarithm of <math>n</math> is <math>m</math> means <math>n \equiv 2^m \pmod 11</math>:		2 is a [[primitive root]] mod 11, so we can take it as the base of the discrete logarithm. We thus get an explicit bijection from the additive group of integers mod 10 to the multiplicative group of nonzero congruence classes mod 11, given by <math>m \mapsto 2^m</math>. The inverse of that mapping is the discrete logarithm, i.e., the discrete logarithm of <math>n</math> is <math>m</math> means <math>n \equiv 2^m \pmod {11}</math>:

	{\| class="sortable" border="1"		{\| class="sortable" border="1"

Vipul at 22:38, 2 January 2012

2012-01-02T22:38:44Z

@@ Line 19: / Line 19: @@
 |-
 | [[satisfies property::regular prime]] || fourth regular prime || {{#lst:regular prime|list}} ||
 |}

Vipul: Created page with "{{particular natural number}} ==Summary== ===Factorization=== The number 11 is a prime number. ===Properties and families=== {| class="sortable" border="1" ! Property..."

2012-01-02T22:06:01Z

Created page with "{{particular natural number}} ==Summary== ===Factorization=== The number 11 is a prime number. ===Properties and families=== {| class="sortable" border="1" ! Property..."

New page

{{particular natural number}}

==Summary==

===Factorization===

The number 11 is a [[prime number]].

===Properties and families===

{| class="sortable" border="1"
! Property or family !! Parameter values !! First few numbers !! Proof of satisfaction/containment/membership
|-
| [[satisfies property::prime number]] || fifth prime number || {{#lst:prime number|list}} || divide and check
|-
| [[satisfies property::safe prime]] (prime that is of the form <math>2q + 1</math> for other prime <math>q</math>) || third safe prime || {{#lst:safe prime|list}} ||
|-
| [[satisfies property::Sophie Germain prime]] (prime <math>p</math> such that <math>2p + 1</math> is prime) || fourth Sophie Germain prime || {{#lst:Sophie Germain prime|list}} ||
|-
| [[satisfies property::regular prime]] || fourth regular prime || {{#lst:regular prime|list}} ||
|}