How to make sure two tables have the same width?

if you use begin{table}{ p{3cm} p{8cm} } you can control the exact width of the columns. Do mind that if you want vertical rules between columns they also take a bit of width. (I do not know the exact amount)

One way to assure that the overall widths of two three-column tables are the same is to (a) choose an overall width for both tables (say, 0.7textwidth) (b) use a tabularx environment instead of a tabular environment and set the widths of both tabualarx environments to the chosen width, and (c) assign the X column type to at least one column in both tables. That way, within bounds, LaTeX can vary the widths of the X-type column(s) to make up for variations in the widths of the other columns.

In the code below, both tables' widths are set to 0.7textwidth and the first column of both tables is assigned type X. The overall width of the third column is the same in both tables. Observe that the middle column in the second table is wider the one in the upper. The second table makes up for the increased width of the second by automatically reducing the width of the first column.

The tables are also set up in a way to assign automatic math mode to the final two columns; this allowed me to get rid of lots of $ symbols, significantly decluttering the code.

documentclass[a4paper, 11pt, oneside]{book}
bibliographystyle{plainnat}

usepackage[margin=3cm]{geometry}
usepackage[T1]{fontenc}
usepackage[utf8]{inputenc}
usepackage{mathtools,amssymb,amsthm}
usepackage{etoolbox,fancyhdr,graphicx}
usepackage{tabularx,booktabs,lmodern}
newcolumntype{C}{>{$}c<{$}} % automatic math mode, centered
newcolumntype{L}{>{$}l<{$}} % automatic math mode, left-aligned 

usepackage{lmodern}    
usepackage{mdframed,pgf,tikz,tcolorbox}
usepackage[flushleft]{threeparttable}

begin{document}
begin{table}[ht]
centering

begin{tabularx}{0.7textwidth}{@{}XLC@{}}
toprule
Operation & & $Bit Complexity$ 
midrule
Addition        &a+b          &mathcal{O}(log(ab)+) 
Subtraction     &a-b          &mathcal{O}(log(ab)) 
Multiplication  &a cdot b    &mathcal{O}(log^2(ab)) 
Division with remainder &a = k cdot b + r &mathcal{O}(log^2(ab))
bottomrule
end{tabularx}
caption{Bit complexity of elementary operations in $mathbb{Z}$.}
label{tab:table_1}

vspace{8mm}
begin{tabularx}{0.7textwidth}{@{}XLC@{}}
toprule
multicolumn{2}{@{}c}{Operation} & $Bit Complexity$ 
midrule
Modular Addition       &a+b bmod n         &mathcal{O}(log(n)) 
Modular Subtraction    &a-b bmod n         &mathcal{O}(log(n)) 
Modular Multiplication &a cdot b bmod n   &mathcal{O}(log^2(n)) 
Modular Inversion      &a^{-1} bmod n      &mathcal{O}(log^2(n)) 
Modular Exponentiation &a^k bmod n, k < n &mathcal{O}(log^3(n)) 
bottomrule
end{tabularx}
caption{Bit complexity of elementary operations in $mathbb{Z} / n mathbb{Z}$.}
label{tab:table_2}
end{table}

end{document}