Euler Totient Function & Miller-Rabin Primality Test

---

Part 1: Euler Totient Function

The Euler Totient Function, denoted $\phi(n)$, is defined as the number of positive integers less than or equal to $n$ that are relatively prime (coprime) to $n$.

$$\phi(n) = |{ k : 1 \le k \le n,\ \gcd(k, n) = 1 }|$$

Key properties:

• If $p$ is prime: $\phi(p) = p - 1$
• For a prime power: $\phi(p^k) = p^k - p^{k-1}$
• Multiplicative: $\phi(mn) = \phi(m)\cdot\phi(n)$ when $\gcd(m,n) = 1$

Example: $\phi(37) = 36$ since 37 is prime.

---

Part 2: Miller-Rabin Test on $n = 37$

Algorithm

To test $n$ with a chosen witness $a$:

1. Write $n - 1 = 2^s \cdot d$ with $d$ odd.
2. Compute $x = a^d \bmod n$.
3. If $x \equiv 1$ or $x \equiv -1 \pmod n$ → probably prime.
4. Otherwise square $x$ repeatedly (for $r = 1, \dots, s-1$); if any gives $-1 \pmod n$ → probably prime.
5. If none hold → composite.

---

Step 1: Express $n - 1 = 2^s \cdot d$

$$n - 1 = 36 = 2^2 \cdot 9$$

So $s = 2$, $d = 9$.

---

Step 2: Choose witness $a = 2$, compute $a^d \bmod n$

$$2^9 \bmod 37$$

• $2^1 = 2$
• $2^2 = 4$
• $2^4 = 16$
• $2^8 = 256 = 6\times 37 + 34 \equiv 34 \pmod{37}$
• $2^9 = 2^8 \cdot 2 = 34 \times 2 = 68 \equiv 68 - 37 = 31 \pmod{37}$

$$x = 2^9 \equiv 31 \pmod{37}$$

---

Step 3: Check conditions

Initial check: Is $x \equiv 1$ or $x \equiv 36\ (\equiv -1)$? $$31 \ne 1, \quad 31 \ne 36 \quad \Rightarrow \text{ not yet passed}$$

Square once ($r = 1$): compute $2^{18} = x^2 \bmod 37$ $$31^2 = 961, \quad 961 = 25\times 37 + 36 = 925 + 36$$ $$2^{18} \equiv 36 \equiv -1 \pmod{37} \quad \checkmark$$

Condition satisfied.

---

Conclusion

Since $2^{18} \equiv -1 \pmod{37}$, the test passes for witness $a = 2$.

$$\boxed{37 \text{ is PROBABLY PRIME (not composite)}}$$

37 is in fact a prime number, so Miller-Rabin correctly reports it as not composite.

Security Risk Assessment

Definition

Security Risk Assessment is a systematic process of identifying, analyzing, and evaluating potential security threats and vulnerabilities within an information system or organization. It helps determine the likelihood and impact of security incidents and guides decision-making for implementing appropriate security controls and countermeasures.

Note: The reference notes did not contain material on this topic; the following answer is based on standard information security curriculum content.

---

Aspects of a Successful Security Risk Assessment

A successful security risk assessment involves the following key aspects:

1. Asset Identification

• Identify all valuable assets within the organization (hardware, software, data, personnel, processes).
• Determine the value and criticality of each asset to the organization.

2. Threat Identification

• Identify potential threats that could harm the identified assets.
• Threats may be natural (floods, fire), human (hackers, insiders), or environmental (power failure).

3. Vulnerability Assessment

• Identify weaknesses or gaps in existing security controls.
• Vulnerabilities can exist in software, hardware, policies, or procedures.

4. Risk Analysis

• Evaluate the likelihood of a threat exploiting a vulnerability.
• Estimate the potential impact or damage if the risk materializes.
• Risk is commonly expressed as:

$$\text{Risk} = \text{Likelihood} \times \text{Impact}$$

5. Risk Evaluation and Prioritization

• Compare analyzed risks against acceptable risk criteria.
• Prioritize risks based on their severity to focus resources effectively.

6. Risk Treatment / Mitigation

• Select appropriate controls to:
  • Avoid the risk
  • Reduce the risk (mitigation)
  • Transfer the risk (e.g., insurance)
  • Accept the risk (if within tolerance)

7. Documentation and Reporting

• Document all findings, risk levels, and recommended controls.
• Provide a clear report to management for informed decision-making.

8. Monitoring and Review

• Continuously monitor the risk environment.
• Reassess risks periodically as systems, threats, and business needs change.

---

Summary Table

---

A well-conducted security risk assessment forms the foundation of an effective information security management system (ISMS) and helps organizations protect their assets proactively.