341 - Revision history

Vipul: /* Abstract structure */

2012-01-05T00:11:57Z

Abstract structure

← Older revision		Revision as of 00:11, 5 January 2012
Line 36:		Line 36:
	===Abstract structure===		===Abstract structure===

	{{~~square-free number~~ multiplicative group facts to check against}}		{{multiplicative group facts to check against}}

	By the [[Chinese remainder theorem]], we have the ring decomposition:		By the [[Chinese remainder theorem]], we have the ring decomposition:

Vipul: /* Summary */

2012-01-04T23:43:44Z

Summary

← Older revision		Revision as of 23:43, 4 January 2012
Line 61:		Line 61:
	! Primality test !! Relies on ... !! Total number of candidate bases !! Number of bases wih gcd more than 1 !! Number of witnesses that are relatively prime !! Number of liars that are relatively prime !! Total number of witnesses !! Probability of picking witness !! Probability of picking liar !! Conditional probability of picking witness for relatively prime !! Conditional probability of picking liar for relatively prime		! Primality test !! Relies on ... !! Total number of candidate bases !! Number of bases wih gcd more than 1 !! Number of witnesses that are relatively prime !! Number of liars that are relatively prime !! Total number of witnesses !! Probability of picking witness !! Probability of picking liar !! Conditional probability of picking witness for relatively prime !! Conditional probability of picking liar for relatively prime
	\|-		\|-
	\| [[Fermat primality test]] \|\| [[Fermat's little theorem]] \|\| 340 \|\| 40 \|\| 200 \|\| 100 \|\| 240/340 = 12/17 \|\| 100/340 = 5/17 \|\| 2/3 \|\| 1/3		\| [[Fermat primality test]] \|\| [[Fermat's little theorem]] \|\| 340 \|\| 40 \|\| 200 \|\| 100 \|\| 240 \|\| 240/340 = 12/17 \|\| 100/340 = 5/17 \|\| 2/3 \|\| 1/3
	\|-		\|-
	\| [[Solovay-Strassen primality test]] \|\| [[Euler's criterion]] \|\| 340 \|\| 40 \|\| ? \|\| ? \|\| ? \|\| ? \|\| ? \|\| ?		\| [[Solovay-Strassen primality test]] \|\| [[Euler's criterion]] \|\| 340 \|\| 40 \|\| ? \|\| ? \|\| ? \|\| ? \|\| ? \|\| ? \|\| ?
	\|-		\|-
	\| [[Miller-Rabin primality test]] \|\| \|\| 340 \|\| 40 \|\| ? \|\| ? \|\| ? \|\| ? \|\| ? \|\| ?		\| [[Miller-Rabin primality test]] \|\| \|\| 340 \|\| 40 \|\| ? \|\| ? \|\| ? \|\| ? \|\| ? \|\| ? \|\| ?
	\|}		\|}

Vipul: /* Summary */

2012-01-04T23:43:05Z

Summary

← Older revision		Revision as of 23:43, 4 January 2012
Line 57:		Line 57:

	===Summary===		===Summary===

			{\| class="sortable" border="1"
			! Primality test !! Relies on ... !! Total number of candidate bases !! Number of bases wih gcd more than 1 !! Number of witnesses that are relatively prime !! Number of liars that are relatively prime !! Total number of witnesses !! Probability of picking witness !! Probability of picking liar !! Conditional probability of picking witness for relatively prime !! Conditional probability of picking liar for relatively prime
			\|-
			\| [[Fermat primality test]] \|\| [[Fermat's little theorem]] \|\| 340 \|\| 40 \|\| 200 \|\| 100 \|\| 240/340 = 12/17 \|\| 100/340 = 5/17 \|\| 2/3 \|\| 1/3
			\|-
			\| [[Solovay-Strassen primality test]] \|\| [[Euler's criterion]] \|\| 340 \|\| 40 \|\| ? \|\| ? \|\| ? \|\| ? \|\| ? \|\| ?
			\|-
			\| [[Miller-Rabin primality test]] \|\| \|\| 340 \|\| 40 \|\| ? \|\| ? \|\| ? \|\| ? \|\| ? \|\| ?
			\|}

	===Fermat test===		===Fermat test===

Vipul: /* Fermat test */

2012-01-04T22:59:44Z

Fermat test

← Older revision		Revision as of 22:59, 4 January 2012
Line 60:		Line 60:
	===Fermat test===		===Fermat test===

	A base <math>a</math> ~~is a Fermat pseudoprime mod 341~~ if the order of <math>a</math> mod 11 divides 340 and the order of <math>a</math> mod 31 divides 340. The first condition always holds, because 11 - 1 = 10 divides 340. The second condition is equivalent to the order dividing 10, which holds for 1/3 of the bases relatively prime to 31. Overall, 341 is a [[Fermat pseudoprime]] for 1/3 of the 300 possible bases relatively prime to it (i.e., a total of 100 possible bases). This means that if we use the Fermat test for a base picked at random, there is a 2/3 chance that we will be able to use it to conclude that 341 is not prime.		341 is a Fermat pseudoprime to base <math>a</math> if the order of <math>a</math> mod 11 divides 340 and the order of <math>a</math> mod 31 divides 340. The first condition always holds, because 11 - 1 = 10 divides 340. The second condition is equivalent to the order dividing 10, which holds for 1/3 of the bases relatively prime to 31. Overall, 341 is a [[Fermat pseudoprime]] for 1/3 of the 300 possible bases relatively prime to it (i.e., a total of 100 possible bases). This means that if we use the Fermat test for a base picked at random, there is a 2/3 chance that we will be able to use it to conclude that 341 is not prime.

	2 is one of the bases for which 341 is a Fermat pseudoprime, because <math>2^{10} = 1024 \equiv 1 \pmod {341}</math>. Thus, 341 is a [[Poulet number]] or Sarrus number.		2 is one of the bases for which 341 is a Fermat pseudoprime, because <math>2^{10} = 1024 \equiv 1 \pmod {341}</math>. Thus, 341 is a [[Poulet number]] or Sarrus number.

Vipul: /* Abstract structure */

2012-01-04T22:56:13Z

Abstract structure

← Older revision		Revision as of 22:56, 4 January 2012
Line 46:		Line 46:
	<math>(\mathbb{Z}/341\mathbb{Z})^* \cong (\mathbb{Z}/11\mathbb{Z})^* \times (\mathbb{Z}/31\mathbb{Z})^*</math>		<math>(\mathbb{Z}/341\mathbb{Z})^* \cong (\mathbb{Z}/11\mathbb{Z})^* \times (\mathbb{Z}/31\mathbb{Z})^*</math>

	Both groups on the right side are cyclic with orders 10 and 30 respectively, so the whole group has order <math>10 \times 30 = 300</math> (the order of the multiplicative group is termed the [[Euler totient function]] and denoted <math>\varphi</math>, so this is saying that <math>\varphi(341) = 300</math>).		Both groups on the right side are cyclic with orders 10 and 30 respectively, so the whole group is:

			<math>(\mathbb{Z}/341\mathbb{Z})^* \cong \mathbb{Z}/10\mathbb{Z} \times \mathbb{Z}/30\mathbb{Z}</math>

			This group has order <math>10 \times 30 = 300</math> (the order of the multiplicative group is termed the [[Euler totient function]] and denoted <math>\varphi</math>, so this is saying that <math>\varphi(341) = 300</math>).

	The exponents of the factor groups are 10 and 30 respectively, hence the exponent of the whole group is the lcm of these, which is 30. The exponent of the multiplicative group is termed the [[universal exponent]] and denoted <math>\lambda</math>, so this is saying that <math>\lambda(341) = 30</math>).		The exponents of the factor groups are 10 and 30 respectively, hence the exponent of the whole group is the lcm of these, which is 30. The exponent of the multiplicative group is termed the [[universal exponent]] and denoted <math>\lambda</math>, so this is saying that <math>\lambda(341) = 30</math>).

Vipul: /* Fermat test */

2012-01-03T21:54:21Z

Fermat test

← Older revision		Revision as of 21:54, 3 January 2012
Line 56:		Line 56:
	===Fermat test===		===Fermat test===

	A base <math>a</math> is a Fermat pseudoprime mod 341 if the order of <math>a</math> mod 11 divides 340 and the order of <math>a</math> mod 31 divides 340. The first condition always holds, because 11 - 1 = 10 divides 340. The second condition is equivalent to the order dividing 10, which holds for 1/3 of the bases relatively prime to 31. Overall, 341 is a [[Fermat pseudoprime]] for 1/3 of the 300 possible bases relatively prime to it (i.e., a total of 100 possible bases). This means that if we ~~pick~~ use the Fermat test for a base picked at random, there is a 2/3 chance that we will be able to use it to conclude that 341 is not prime.		A base <math>a</math> is a Fermat pseudoprime mod 341 if the order of <math>a</math> mod 11 divides 340 and the order of <math>a</math> mod 31 divides 340. The first condition always holds, because 11 - 1 = 10 divides 340. The second condition is equivalent to the order dividing 10, which holds for 1/3 of the bases relatively prime to 31. Overall, 341 is a [[Fermat pseudoprime]] for 1/3 of the 300 possible bases relatively prime to it (i.e., a total of 100 possible bases). This means that if we use the Fermat test for a base picked at random, there is a 2/3 chance that we will be able to use it to conclude that 341 is not prime.

	2 is one of the bases for which 341 is a Fermat pseudoprime, because <math>2^{10} = 1024 \equiv 1 \pmod {341}</math>. Thus, 341 is a [[Poulet number]] or Sarrus number.		2 is one of the bases for which 341 is a Fermat pseudoprime, because <math>2^{10} = 1024 \equiv 1 \pmod {341}</math>. Thus, 341 is a [[Poulet number]] or Sarrus number.

Vipul: /* Fermat test */

2012-01-03T21:54:07Z

Fermat test

← Older revision		Revision as of 21:54, 3 January 2012
Line 56:		Line 56:
	===Fermat test===		===Fermat test===

	A base <math>a</math> is a Fermat pseudoprime mod 341 if the order of <math>a</math> mod 11 divides 340 and the order of <math>a</math> mod 31 divides 340. The first condition always holds, because 11 - 1 = 10 divides 340. The second condition is equivalent to the order dividing 10, which holds for 1/3 of the bases relatively prime to 31. Overall, 341 is a [[Fermat pseudoprime]] for 1/3 of the possible bases relatively prime to it. This means that if we pick use the Fermat test for a base picked at random, there is a 2/3 chance that we will be able to use it to conclude that 341 is not prime.		A base <math>a</math> is a Fermat pseudoprime mod 341 if the order of <math>a</math> mod 11 divides 340 and the order of <math>a</math> mod 31 divides 340. The first condition always holds, because 11 - 1 = 10 divides 340. The second condition is equivalent to the order dividing 10, which holds for 1/3 of the bases relatively prime to 31. Overall, 341 is a [[Fermat pseudoprime]] for 1/3 of the 300 possible bases relatively prime to it (i.e., a total of 100 possible bases). This means that if we pick use the Fermat test for a base picked at random, there is a 2/3 chance that we will be able to use it to conclude that 341 is not prime.

	2 is one of the bases for which 341 is a Fermat pseudoprime, because <math>2^{10} = 1024 \equiv 1 \pmod {341}</math>. Thus, 341 is a [[Poulet number]] or Sarrus number.		2 is one of the bases for which 341 is a Fermat pseudoprime, because <math>2^{10} = 1024 \equiv 1 \pmod {341}</math>. Thus, 341 is a [[Poulet number]] or Sarrus number.

Vipul: /* Abstract structure */

2012-01-03T21:53:14Z

Abstract structure

← Older revision		Revision as of 21:53, 3 January 2012
Line 46:		Line 46:
	<math>(\mathbb{Z}/341\mathbb{Z})^* \cong (\mathbb{Z}/11\mathbb{Z})^* \times (\mathbb{Z}/31\mathbb{Z})^*</math>		<math>(\mathbb{Z}/341\mathbb{Z})^* \cong (\mathbb{Z}/11\mathbb{Z})^* \times (\mathbb{Z}/31\mathbb{Z})^*</math>

	Both groups on the right side are cyclic with orders 10 and 30 respectively, so the whole group has order <math>10 \times 30 = 300</math>~~. That's~~ the [[Euler totient function]] of 341.		Both groups on the right side are cyclic with orders 10 and 30 respectively, so the whole group has order <math>10 \times 30 = 300</math> (the order of the multiplicative group is termed the [[Euler totient function]] and denoted <math>\varphi</math>, so this is saying that <math>\varphi(341) = 300</math>).

	The exponents of the factor groups are 10 and 30 respectively, hence the exponent of the whole group is the lcm of these, which is 30.		The exponents of the factor groups are 10 and 30 respectively, hence the exponent of the whole group is the lcm of these, which is 30. The exponent of the multiplicative group is termed the [[universal exponent]] and denoted <math>\lambda</math>, so this is saying that <math>\lambda(341) = 30</math>).

	==Primality testing==		==Primality testing==

Vipul: /* Structure of integers mod 341 */

2012-01-03T21:51:34Z

Structure of integers mod 341

← Older revision		Revision as of 21:51, 3 January 2012
Line 35:		Line 35:

	===Abstract structure===		===Abstract structure===

			{{square-free number multiplicative group facts to check against}}

	By the [[Chinese remainder theorem]], we have the ring decomposition:		By the [[Chinese remainder theorem]], we have the ring decomposition:

Vipul: /* Arithmetic functions */

2012-01-03T21:50:15Z

Arithmetic functions

← Older revision		Revision as of 21:50, 3 January 2012
Line 31:		Line 31:
	\| {{arithmetic function value\|Mobius function\|1}} \|\| The number is square-free and has an even number of prime divisors (2 prime divisors).		\| {{arithmetic function value\|Mobius function\|1}} \|\| The number is square-free and has an even number of prime divisors (2 prime divisors).
	\|}		\|}

			==Structure of integers mod 341==

			===Abstract structure===

			By the [[Chinese remainder theorem]], we have the ring decomposition:

			<math>\mathbb{Z}/341\mathbb{Z} \cong \mathbb{Z}/11\mathbb{Z} \times \mathbb{Z}/31\mathbb{Z}</math>

			For the multiplicative group, this gives:

			<math>(\mathbb{Z}/341\mathbb{Z})^* \cong (\mathbb{Z}/11\mathbb{Z})^* \times (\mathbb{Z}/31\mathbb{Z})^*</math>

			Both groups on the right side are cyclic with orders 10 and 30 respectively, so the whole group has order <math>10 \times 30 = 300</math>. That's the [[Euler totient function]] of 341.

			The exponents of the factor groups are 10 and 30 respectively, hence the exponent of the whole group is the lcm of these, which is 30.

			==Primality testing==

			===Summary===

			===Fermat test===

			A base <math>a</math> is a Fermat pseudoprime mod 341 if the order of <math>a</math> mod 11 divides 340 and the order of <math>a</math> mod 31 divides 340. The first condition always holds, because 11 - 1 = 10 divides 340. The second condition is equivalent to the order dividing 10, which holds for 1/3 of the bases relatively prime to 31. Overall, 341 is a [[Fermat pseudoprime]] for 1/3 of the possible bases relatively prime to it. This means that if we pick use the Fermat test for a base picked at random, there is a 2/3 chance that we will be able to use it to conclude that 341 is not prime.

			2 is one of the bases for which 341 is a Fermat pseudoprime, because <math>2^{10} = 1024 \equiv 1 \pmod {341}</math>. Thus, 341 is a [[Poulet number]] or Sarrus number.

			===Euler test===

			{{fillin}}

			===Strong Fermat test===

			{{fillin}}